Theorems on Solutions of Linear Equations

Rank of a Matrix

Let \(\,\boldsymbol{A}\ \) be a matrix with \(\,m\,\) rows \(\ \ \text{and}\ \ \,n\ \) columns over a field \(\,K:\ \,\boldsymbol{A}\,\in M_{m\times n}(K). \\\)

Definition. \(\,\)

The row rank \(\,\) of the matrix \(\,\boldsymbol{A}\ \,\) is the number of linearly independent rows of this matrix. \(\\\) Similarly, the \(\,\) column rank \(\,\) is the number of linearly independent columns.

Theorem. \(\,\)

The column rank is equal to the row rank of the matrix.

It makes sense then to talk about the rank of the matrix \(\,\boldsymbol{A},\,\) which is equal to its number of linearly independent rows or columns. We denote it by \(\ \text{rk}\,\boldsymbol{A}.\)

Corollary 1. \(\\\) The rank of the matrix cannot be greater than any of its two dimensions: \(\ \,\text{rk}\boldsymbol{A}\,\leq\,m,n.\)

Corollary 2. \(\\\) The rank of the matrix equals the dimension of the space spanned by its rows, \(\\\) and also to the dimension of the space spanned by its columns. \(\\\)

Theorem. \(\,\)

Elementary operations on rows or columns do not change rank of the matrix.

The rank of the matrix is equal then to the number of leading unities in its reduced row echelon form.

Theorem. \(\,\)

The rank of the matrix is equal to the highest order of its non-zero minors.

We will apply the aforementioned methods to determine rank of a given matrix by using functions built in Sage. \(\\\)

Rank of the matrix is given by a direct function rank():

sage: A = matrix(QQ,[[2, 3, 5,-3,-2],
                     [3, 4, 3,-1,-3],
                     [5, 6,-1, 3,-5]])

sage: rk_A = A.rank()
sage: print "Rank of the matrix A is", rk_A

Rank of the matrix A is 2

The methods row_space() and column_space() create a space spanned by rows \(\\\) and columns of the matrix, \(\,\) while dimension() provides a dimension of the space:

sage: Vrow = A.row_space()
sage: Vcol = A.column_space()
sage: print "Dimension of the row space of matrix A:", Vrow.dimension()
sage: print "Dimension of the column space of matrix A:", Vcol.dimension()

Dimension of the row space of matrix A: 2
Dimension of the column space of matrix A: 2

In reduced row echelon form the matrix \(\,\boldsymbol{A}\,\) has two leading unities:

sage: table([["A", "=", A, '$\\rightarrow$', A.rref()]])

\[\begin{split}A\quad =\quad \left(\begin{array}{rrrrr} 2 & 3 & 5 & -3 & -2 \\ 3 & 4 & 3 & -1 & -3 \\ 5 & 6 & -1 & 3 & -5 \end{array}\right)\quad\rightarrow\quad\left(\begin{array}{rrrrr} 1 & 0 & -11 & 9 & -1 \\ 0 & 1 & 9 & -7 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right)\,.\end{split}\]

The method minors(k) provides a list of all the minors of order \(\,k\ \) of the given matrix:

sage: print A.minors(2)
sage: print ""
sage: print A.minors(3)

[-1, -9, 7, 0, -11, 9, -1, 4, -9, 7, -3, -27, 21, 0, -33, 27, -3, 12,
-27, 21, -2, -18, 14, 0, -22, 18, -2, 8, -18, 14]

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

As one can see, the matrix \(\,\boldsymbol{A}\ \) has non-zero minors of order two, whereas all the minors of order three vanish. \(\\\)

Eventually, each of the methods used gives the same result: \(\ \,\text{rk}\,\boldsymbol{A} = 2.\)

General Solution of a System of Equations

We consider a (nonhomogeneous) system of linear equations given by a matrix equation of the form

(1)\[\boldsymbol{A}\,\boldsymbol{x}\,=\,\boldsymbol{b}\]

and the corresponding homogeneous system

(2)\[\boldsymbol{A}\,\boldsymbol{x}\,=\,\boldsymbol{0}\,,\]

where \(\,\boldsymbol{A}\,\in M_{m\times n}(K)\,\) and \(\,\boldsymbol{b}\in K^m.\)

A necessary and sufficient condition for any solution to exist provides

Theorem 0. \(\,\) (Kronecker-Capelli) \(\,\)

A system of linear equations (1) has a solution (is consistent) if and only if the rank of its coefficient matrix is equal to the rank of its augmented matrix:

(3)\[\text{rk}\,\boldsymbol{A}\,=\,\text{rk}\,\boldsymbol{B}\,,\qquad \text{where}\quad\boldsymbol{B}\,=\,[\,\boldsymbol{A}\,|\,\boldsymbol{b}\,].\]

For the homogeneous system (2) the condition (3) is always fulfilled, because adding a zero column does not change the rank of the matrix. Hence, the homogeneous system is always consistent \(\,\) - \(\,\) there always exists at least a zero solution \(\,\boldsymbol{x} = \boldsymbol{0}.\,\) The existence of non-zero solutions explains

Theorem 1. \(\,\)

The homogeneous system of equations (2) has non-zero solutions if and only if the rank of its coefficient matrix is smaller than the number of unknowns: \(\ \ \text{rk}\boldsymbol{A}\,<\,n\,.\)

In particular, the non-zero solutions exist if the number of equations is smaller than the number of unknowns, that is when \(\,m<n.\)

Let us consider an important case of \(\ \,m=n.\ \,\) Then the condition \(\ \,\text{rk}\boldsymbol{A}<n\ \,\) is satisfied if and only if \(\ \det\boldsymbol{A}=0.\ \,\) Hence, and also by Cramer’s formulae follows

Theorem 1a.

The homogeneous system of equations given by the square matrix \(\,\boldsymbol{A}\,\) has non-zero solutions if and only if \(\ \det\boldsymbol{A}=0.\)

\(\;\)

Denote by \(\ S\ \,\) and \(\ \,S_0\ \) the sets of solutions for the systems \(\,\) (1) \(\ \) and \(\ \,\) (2) :

(4)\[S\ :\,=\ \{\,\boldsymbol{X}\in K^n:\ \boldsymbol{A}\boldsymbol{X}\,=\,\boldsymbol{b}\,\}\,, \qquad S_0\ :\,=\ \{\,\boldsymbol{X}\in K^n:\ \boldsymbol{A}\boldsymbol{X}\,=\,\boldsymbol{0}\,\}\,.\]

Due to the nature of matrix multiplication, it follows that if both \(\,\boldsymbol{X}_1,\,\boldsymbol{X}_2,\,\) are in the set \(\,S_0,\,\) then so is their every linear combination \(\,a_1\boldsymbol{X}_1+a_2\boldsymbol{X}_2,\ \,a_1,a_2\in K:\)

\[\boldsymbol{A}\boldsymbol{X}_1=\boldsymbol{A}\boldsymbol{X}_2=\boldsymbol{0} \qquad\Rightarrow\qquad \boldsymbol{A}\ (a_1\boldsymbol{X}_1+\,a_2\boldsymbol{X}_2)\ =\ a_1\,\boldsymbol{A}\boldsymbol{X}_1\,+\ a_2\,\boldsymbol{A}\boldsymbol{X}_2\ =\ \boldsymbol{0}\,.\]

This means that the set \(\,S_0\,\) is a subspace of the space \(\,K^n\,.\ \) More precisely,

Theorem 2. \(\,\)

The set \(\,S_0\,\) of solutions of the homogeneous system of equations (2) is a vector space (a subspace of the space \(\,K^n\)), whose dimension is equal to the dieference of the number of unknowns and the rank of the coefficient matrix:

\[\text{dim}\,S_0\ =\ n - \text{rk}\boldsymbol{A}\,.\]

We should emphasize that the set \(\,S\,\) of solutions of the nonhomogeneous system of equations (1) is not a vector space (namely, it is a linear variety). If \(\,\text{rk}\boldsymbol{A} = n,\,\) then \(\,\text{dim}\,S_0 = 0,\,\) that is the space \(\,S_0\,\) is reduced to the set containing only one element, the zero vector. This means (in accordance with Theorem 1.) that the system of equations has only the zero solution.

A relation between the solution sets \(\ S\ \,\) and \(\ \,S_0\ \) defined in (4) presents

Theorem 3. \(\,\)

Let \(\,\boldsymbol{X'}\,\) be a particular solution of the system (1):

\[\boldsymbol{A}\boldsymbol{X'} =\ \boldsymbol{b}\,.\]

Then the set \(\,S\,\) of all the solutions of the system (1) may be obtained by adding \(\,\boldsymbol{X'}\,\) \(\\\) to each solution of the system (2) from the set \(\,S_0 :\)

\[S\ =\ \{\,\boldsymbol{X'}\}\ +\ S_0\,.\]

In this way the general solution of the nonhomogeneous system of linear equations is a sum of a particular solution of this system and the general solution of the corresponding homogeneous system.

Corollary. \(\,\)

The nonhomogeneous system (1) has precisely one solution if and only if the rank of the coefficient matrix equals the number of the unknowns: \(\ \text{rk}\boldsymbol{A} = n\,.\ \)

Hence, at least in general, in order to solve a nonhomogeneous system, it suffices to find (or guess) its particular solution and solve the corresponding homogeneous system.

Systems of Linear Equations in Sage

According to Theorem 3., \(\,\) the solution of a system of linear equations

\[\boldsymbol{A}\,\boldsymbol{x}\,=\,\boldsymbol{b}\]

where \(\,\boldsymbol{A}\,\in M_{m\times n}(K)\,\) and \(\,\boldsymbol{b}\in K^m,\ \) may be obtained in two stages:

1. \(\,\) finding a particular solution of the system;

2. \(\,\) calculation of the general solution of the homogeneous system associated with the original one.

To this end the two methods in Sage may be used:

• A.solve_right(b) or in short A\b yields a particular solution of the system;

• A.right_kernel_matrix() returns a matrix, whose rows form basis of the space \(\,S_0\,\) of solutions of the associated homogeneous system.

Example. \(\,\) Consider the system over rational field \(\,Q:\)

\[\begin{split}\begin{array}{l} 3\,x_1\ -\ 2\,x_2\ +\ 5\,x_3\ +\ 4\,x_4\ =\ 2 \\ 6\,x_1\ -\ 4\,x_2\ +\ 4\,x_3\ +\ 3\,x_4\ =\ 3 \\ 9\,x_1\ -\ 6\,x_2\ +\ 3\,x_3\ +\ 2\,x_4\ =\ 4 \end{array}\end{split}\]

sage: A = matrix(QQ,[[3,-2, 5, 4],
                     [6,-4, 4, 3],
                     [9,-6, 3, 2]])

sage: b = vector(QQ,[2,3,4])

# A particular solution:
sage: X = A.solve_right(b)

# Rows of the matrix B0 form basis of the space
# of solutions of the homogeneous system:
sage: B0 = A.right_kernel_matrix()

sage: show((X, B0))

\[\begin{split}\left(\quad\left(\ \frac{7}{18}\,,\ 0\,,\ \frac{1}{6}\,,\ 0\ \right),\quad \left(\ \begin{array}{rrrr} 1 & 0 & -15 & 18 \\ 0 & 1 & 10 & -12 \end{array}\ \right)\quad\right)\end{split}\]

sage: # Verification of the results:
sage: A*X==b, A*B0.transpose()==zero_matrix(QQ,3,2)

(True, True)

\(\;\)

Hence, the general solution of the system consists of the vecors of the form

\[ \begin{align}\begin{aligned}\begin{split}\\\end{split}\\\begin{split}\left[\begin{array}{r} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array}\right]\quad =\quad \left[\begin{array}{c} \small{7/18} \\ 0 \\ \small{1/6} \\ 0 \end{array}\right]\ \ +\ \ s\ \, \left[\begin{array}{r} 1 \\ 0 \\ -15 \\ 18 \end{array}\right]\ \ +\ \ t\ \, \left[\begin{array}{r} 0 \\ 1 \\ 10 \\ -12 \end{array}\right]\,,\qquad s,t\in Q\,.\end{split}\end{aligned}\end{align} \]