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

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 (= null space) of A is called the nullity of A and is denoted by nullity(A).

Since the row vectors of a m-by-n matrix A lie in \( \mathbb{R}^n \) and the column vectors in \( \mathbb{R}^m , \) the row space of A is at most n-dimensional and the column space is at most m-dimensional. Since the rank of A is the common dimension of its row and column space, it follows that

\[ \mbox{rank} ({\bf A}) \le \min (m,n) . \]

Theorem: If A is any matrix, then rank(A) = rank(A^T).

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: If \( T\,:\,V \mapsto W \) is a linear transformation from a finite-dimensional vector space V to a vector space W, then the range of T is finite-dimensional, and

\[ \mbox{rank} (T) + \mbox{nullity}(T) = \dim (V). \]

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 according to 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.

Example. We reconsider the matrix

\[ {\bf M} = \begin{bmatrix} 1&3&-2&7 \\ 4&1&3&5 \\ 2&-5&7&19 \end{bmatrix} = \left[ \begin{array}{ccc|c} 1&3&-2&7 \\ 4&1&3&5 \\ \hline 2&-5&7&19 \end{array} \right] , \]

which we partition into four blocks:

\[ {\bf A}_{2 \times 3} = \begin{bmatrix} 1&3&-2 \\ 4&1&3 \end{bmatrix} , \quad {\bf B}_{2\times 1} = \begin{bmatrix} -7 \\ 5 \end{bmatrix} , {\bf C}_{1 \times 3| = \left[ 2, -5, 7 \right] , \quad {\bf D}_{1\times 1} = \left[ 19 \right] . \]

Now we determine the Schur complement:

\begin{align*} \left( {\bf M} / {\bf D} \right)_{2\times 3} &= {\bf A} - {\bf B} \,{\bf D}^{-1} {\bf C} = \begin{bmatrix} 1&3&-2 \\ 4&1&3 \end{bmatrix} - \begin{bmatrix} -7 \\ 5 \end{bmatrix} \cdot \frac{1}{19} \cdot \left[ 2, -5, 7 \right] \\ &= \begin{bmatrix} 1&3&-2 \\ 4&1&3 \end{bmatrix} - \frac{1}{19} \, \begin{bmatrix} -14&35&-49 \\ 10&-25&35 \end{bmatrix} = \frac{1}{19} \, \begin{bmatrix} 33& 22& 11 \\ 66&44&22 \end{bmatrix} = \frac{11}[19} \, \begin{bmatrix} 3&2&1 \\ 6&4&2 \end{bmatrix} \end{align*}

Since rank of D is 1 and rank of the Schur complement M/D is 1, we get rank of M to be 2. ■

One feature of Sage is that we can easily extend its capabilities by defining new commands. Here will create a function that checks if an augmented matrix represents a consistent system of equations. The syntax is just a bit complicated. lambda is the word that indicates we are making a new function, the input is temporarily named A (think A ugmented), and the name of the function is consistent. Everything following the colon will be evaluated and reported back as the output.

sage: consistent = lambda A: not(A.ncols()-1 in A.pivots())

Execute this block above. There will not be any output, but now the consistent function will be defined and available. Now give it a try (after making sure to have run the code above that defines aug). Note that the output of consistent() will be either True or False.

sage: consistent(aug)
False

The consistent() command works by simply checking to see if the last column of A is not in the list of pivots. We can now test many different augmented matrices, such as perhaps changing the vector of constants while keeping the coefficient matrix fixed. Again, make sure you execute the code above that defines coeff and const.

sage: consistent(coeff.augment(const))
False
sage: w = vector(QQ, [3,1,2])
sage: consistent(coeff.augment(w))
True
sage: u = vector(QQ, [1,3,1])
sage: consistent(coeff.augment(u))
False