Skip to content
Geometry and Algebra

Matrix rank and the Rouché-Capelli theorem

Row and column rank, computing it with Gauss and with minors, proof of the Rouché-Capelli theorem, the structure of solutions and systems with a parameter.

4 min read 0 comments

Rank is the number that says “how much independent information” a matrix holds. It ties together the three previous lessons (systems, determinant, vector spaces) and leads to the Rouché-Capelli theorem, which answers once and for all the question: when does a linear system have solutions, and how many?

Definition

The rank of a matrix A, \operatorname{rank}A, is the largest number of linearly independent columns, that is the dimension of the space spanned by the columns. An important result is that it equals the largest number of independent rows: row rank and column rank are the same. So for an m\times n matrix \operatorname{rank}A \le \min(m, n).

How to compute it

With Gauss. Elementary row operations do not change the rank (they do not change the space spanned by the rows). The rank is therefore the number of pivots in the echelon form, that is the number of non-zero rows.

With minors. A minor of order k is the determinant of a k\times k submatrix. The rank is the largest order of a non-zero minor. To avoid trying them all one uses the bordering theorem (Kronecker’s): if a minor M of order k is non-zero and all minors of order k + 1 that contain it (“bordered” minors) are zero, then the rank is k.

Example.

    \[ A = \begin{pmatrix} 1 & 2 & 0 & 1\\ 2 & 4 & 1 & 3\\ 3 & 6 & 1 & 4 \end{pmatrix} \xrightarrow[R_3 - 3R_1]{R_2 - 2R_1} \begin{pmatrix} 1 & 2 & 0 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 1 \end{pmatrix} \xrightarrow{R_3 - R_2} \begin{pmatrix} 1 & 2 & 0 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 \end{pmatrix} \]

Two pivots: \operatorname{rank}A = 2. Indeed the third row of A is the sum of the first two, and the second column is twice the first.

The Rouché-Capelli theorem

Theorem. The system A\mathbf x = \mathbf b, with n unknowns, has solutions if and only if

    \[ \operatorname{rank}A = \operatorname{rank}(A\,|\,\mathbf b) \]

In that case, calling r the common rank, the solutions depend on n - r free parameters. In particular the solution is unique if and only if r = n.

Proof

A\mathbf x = x_1\mathbf a_1 + \dots + x_n\mathbf a_n is a combination of the columns of A. The system has a solution if and only if \mathbf b is a linear combination of the columns of A, that is if and only if \mathbf b lies in the space spanned by the columns. Then adding \mathbf b as a column does not increase the dimension of that space: \operatorname{rank}(A\,|\,\mathbf b) = \operatorname{rank}A. If instead \mathbf b is not a combination of the columns, adding it raises the rank by one.

For the number of parameters: if \mathbf x_0 is a solution, all the others are \mathbf x_0 + \mathbf y with A\mathbf y = \mathbf 0 (the difference of two solutions solves the homogeneous system). The solution space of the homogeneous system, the kernel of A, has dimension n - r, as we will prove with the rank-nullity theorem in the lesson on linear maps.

In short, the structure of all solutions is:

    \[ \text{solutions of } A\mathbf x = \mathbf b \;=\; \mathbf x_0 \;+\; \text{solutions of } A\mathbf x = \mathbf 0 \]

One particular solution plus the general solution of the homogeneous system: the same structure you meet in the linear differential equations of Analysis 2 and in circuits (forced response plus natural response). It is no coincidence: they are all linear problems.

Systems with a parameter

Exam problems often ask to discuss a system as a parameter k varies.

Example.

    \[ \begin{cases} x + y + z = 1\\ x + ky + z = 1\\ x + y + kz = k \end{cases} \]

The determinant of the coefficient matrix, after subtracting the first row from the others, is that of a triangular matrix:

    \[ \det\begin{pmatrix} 1 & 1 & 1\\ 0 & k - 1 & 0\\ 0 & 0 & k - 1 \end{pmatrix} = (k - 1)^2 \]

  • k \ne 1: \det A \ne 0, rank 3 = number of unknowns, a single solution. From the second equation minus the first, (k - 1)y = 0, so y = 0; from the third minus the first, (k - 1)z = k - 1, so z = 1; finally x = 0. Solution (0, 0, 1).
  • k = 1: all three equations become x + y + z = 1. \operatorname{rank}A = \operatorname{rank}(A\,|\,\mathbf b) = 1, the solutions depend on 3 - 1 = 2 parameters: a plane.

Had the right-hand side of the third equation been 2 instead of k, for k = 1 we would have had \operatorname{rank}A = 1 and \operatorname{rank}(A\,|\,\mathbf b) = 2: an inconsistent system.

Rank and invertibility

For a square n\times n matrix the following are equivalent:

  1. A is invertible;
  2. \det A \ne 0;
  3. \operatorname{rank}A = n;
  4. the columns (and the rows) of A form a basis of \mathbb R^n;
  5. A\mathbf x = \mathbf 0 has only the zero solution;
  6. A\mathbf x = \mathbf b has exactly one solution for every \mathbf b.

This list is one of the most used tools in the course: to prove one property it is enough to prove another.

Related articles

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
0
Would love your thoughts, please comment.x
()
x