Linear Systems of Algebraic Equations

This page presents some topics from Linear Algebra needed for construction of solutions to systems of linear algebraic equations and some applications. We use matrices and vectors as essential elements in obtaining and expressing the solutions.

Rank and Nullity

Rank and Nullity

The common dimension of the row space and the column space of a matrix A is called the rank and is denoted by rank(A); the dimension of the kernel of A is called the nullity of A and is denoted by nullity(A).

Theorem: If A is a matrix with n columns, then rank(A) + nullity(A) = n. ■

Theorem: The rank of a matrix is the order of the largest nonzero determinant that can be obtained from the elements of the matrix. ■

Theorem: If A is a matrix with m rows, then rank(A) + nullity\( \left( {\bf A}^{\mathrm T} \right) =m. \) ■

Theorem: If A is an \( m \times n \) matrix, then

• rank(A) = the number of leading variables or pivots in the general solution of \( {\bf A}\,{\bf x} = {\bf 0}. \)
• rank(A) = the maximum number of linearly independent row vectors in A.
• nullity(A) = the number of parameters in the general solution of \( {\bf A}\,{\bf x} = {\bf 0}. \) ■

Theorem: If A is any matrix, then rank(A) = nullity(\( {\bf A}^{\mathrm T} ).\) ■

Theorem: Suppose that a linear system \( {\bf A}\,{\bf x} = {\bf b} \) with m equations and n variables is consistent. If the coefficient matrice A has the rank r, then the solution of the system contains \( n-r \) parameters. ■

Theorem: Every rank 1 matrix has the special form \( {\bf A} = {\bf u} \,{\bf v}^{\mathrm T} = \) column times row. ■

The columns are multipliers of u. The rows are multipliers of \( {\bf v}^{\mathrm T} .\) The null space is the plane perpendicular to v: (\( {\bf A}{\bf x} = {\bf 0} \) means that \( {\bf u}\left( {\bf v}^{\mathrm T} {\bf x} \right) = {\bf 0} \) and then \( {\bf v}^{\mathrm T} {\bf x} = 0). \)

Example. Consider the system of linear algebraic equations

\[ \begin{split} x_1 + 3\,x_2 - 2\,x_3 &=-7 , \\ 4\,x_1 + x_2 + 3\,x_3 &= 5, \\ 2\,x_1 -5\,x_2 + 7\,x_3 &= 19. \end{split} \]

Applicatying of Gauss-Jordan elimination procedure to the augmented matrix, we get

\[ \left( \begin{array}{ccc|c} 1 & 3 & -2 & -7 \\ 4&1&3&5 \\ 2&-5& 7 & 19 \end{array} \right) \qquad \Longrightarrow \qquad \left( \begin{array}{ccc|c} 1 & 0 & 1 & 2 \\ 0&1&-1&-3 \\ 0&0&0&0 \end{array} \right) . \]

Therefore, rank \( ({\bf A} ) = \mbox{rank} \left( {\bf A} | {\bf b} \right) =2, \) and so the given system is consistent. With \( n=3 , \) we see that the number of parameters in the solution is \( 3-2 =1 . \) ■

Sage computes rank and nullity:

sage: M.rank()
sage: M.right_nullity()

Suppose that a matrix M is partitioned into 2-by-2 blocks \( {\bf M} = \begin{bmatrix} {\bf A} & {\bf B} \\ {\bf C} & {\bf D} \end{bmatrix} .\) Then we immediately obtain the rank additivity formulas

\[ \mbox{rank}({\bf M} ) = \mbox{rank} ({\bf A} ) + \mbox{rank}\left( {\bf M} / {\bf A} \right) = \mbox{rank} ({\bf D} ) + \mbox{rank}\left( {\bf M} / {\bf D} \right) , \]

where Schur complements are

\[ \left( {\bf M} / {\bf A} \right) = {\bf D} - {\bf C}\,{\bf A}^{-1} {\bf B} \qquad \mbox{and} \qquad \left( {\bf M} / {\bf D} \right) = {\bf A} - {\bf B}\,{\bf D}^{-1} {\bf C} . \]

assuming that the indicated inverses exist.