Rank
A matrix can have many rows and columns and still say very little. How many of its rows carry new information, and why does counting its columns give the same number?
Where you are 7 in Row reduction
Why this exists
Sokha, Vanna and Phalla run a coffee roastery. Each blend is a row of grams of four beans: Brazilian, Colombian, Ethiopian and Sumatran. Sokha’s notebook holds four blends,
Blend 3 is blends 1 and 2 poured together. Blend 4 is 3(\text{blend } 2) - 6(\text{blend } 1): no one weighs out a negative amount, but its makeup is still fixed by the first two. Four rows, two pieces of information. That count is the rank, and it says, before any solving, whether a system can be solved for every right-hand side and whether a solution can be unique.
Definition
The rank of a matrix A, written \operatorname{rank} A, is the number of pivot positions of A: the number of leading 1s in its reduced row echelon form. Every echelon form of A has its leading entries at those positions, so the rank is also the number of nonzero rows in any echelon form of A, however it was reached.
Two subspaces come with an m \times n matrix A (Subspaces):
- the row space \operatorname{Row} A, the span of the rows, in \mathbb{R}^n;
- the column space \operatorname{Col} A, the span of the columns, in \mathbb{R}^m.
The transpose A^{T} is the n \times m matrix whose rows are the columns of A, so \operatorname{Row} A^{T} = \operatorname{Col} A (The transpose and symmetric matrices).
Intuition
Row reduction replaces rows by combinations of rows. A row built from the others is eventually canceled to zero; a row that brings something new keeps a leading entry. The rank counts what is left once the repetition is gone.
The columns tell the same story. Every blend of Sokha’s uses three times as much Colombian as Brazilian, so column 2 is 3 times column 1, and the Sumatran is always twice the Brazilian plus the Ethiopian, so column 4 is twice column 1 plus column 3. Two columns are free, two are forced: the count is 2 again. That the two counts always agree is the main theorem here, and it is not obvious, since rows live in \mathbb{R}^n and columns in \mathbb{R}^m.
Results
Rank as a dimension. For every m \times n matrix A,
The nonzero rows of any echelon form of A are a basis of \operatorname{Row} A, and the pivot columns of A itself are a basis of \operatorname{Col} A (Basis and dimension).
Row rank equals column rank. In particular \operatorname{rank} A^{T} = \operatorname{rank} A.
Bounds. \operatorname{rank} A \le m and \operatorname{rank} A \le n; it is 0 only for the zero matrix.
Rank and the system A\mathbf{x} = \mathbf{b}.
- It is consistent exactly when \operatorname{rank} \left[\begin{array}{c|c} A & \mathbf{b} \end{array}\right] = \operatorname{rank} A, that is, when \mathbf{b} is in \operatorname{Col} A.
- It is consistent for every \mathbf{b} in \mathbb{R}^m exactly when \operatorname{rank} A = m.
- A consistent system has exactly one solution when \operatorname{rank} A = n; otherwise it has infinitely many, with n - \operatorname{rank} A free variables (Solving a system by row reduction: one, none or infinitely many solutions).
Why it is true
Row operations keep the row space. Each new row is a combination of old rows, so the new row space sits inside the old. Every row operation can be undone (Augmented matrices and row operations), so the reverse holds too.
The nonzero rows of an echelon form are independent. Suppose c_1\mathbf{r}_1 + \dots + c_k\mathbf{r}_k = \mathbf{0}, rows taken top to bottom. In the column of the leading entry of \mathbf{r}_1 every lower row has 0, so c_1 times a nonzero number is 0: c_1 = 0. Repeat with \mathbf{r}_2, and so on. So these k rows are a basis of \operatorname{Row} A, and \dim \operatorname{Row} A = k = \operatorname{rank} A.
The columns. The Reduced row echelon form lesson proved that the pivot columns of A are linearly independent and every other column is a combination of them. So they are a basis of \operatorname{Col} A, one per pivot. Then \operatorname{rank} A^{T} = \dim \operatorname{Col} A = \operatorname{rank} A.
The system. The reduced form of \left[\begin{array}{c|c} A & \mathbf{b} \end{array}\right] has the pivots of A plus possibly one in the last column, which is a row 0 \; \cdots \; 0 \mid 1, an inconsistent system. If \operatorname{rank} A = m, every row has a pivot of A, so that row cannot appear. If \operatorname{rank} A < m, the reduced form R has a zero last row, \left[\begin{array}{c|c} R & \mathbf{e}_m \end{array}\right] has no solution, and undoing the row operations gives some \left[\begin{array}{c|c} A & \mathbf{b} \end{array}\right] with none either. A consistent system has one solution exactly when every column of A is a pivot column.
Worked examples
Sokha’s notebook
Find the rank of Sokha’s matrix A above, a basis of its row space and a basis of its column space.
SolutionClear column 1 with R_2 - 2R_1 \to R_2 and R_3 - 3R_1 \to R_3:
Column 2 is 0 below row 1, so it gets no pivot. The next pivot is in row 2, column 3; R_3 - R_2 \to R_3 and R_4 - 3R_2 \to R_4 clear below it, leaving rows (1, 3, 0, 2), (0, 0, 1, 1) and two zero rows. So \operatorname{rank} A = 2.
The nonzero rows (1, 3, 0, 2) and (0, 0, 1, 1) are a basis of \operatorname{Row} A; the second is blend 2 minus twice blend 1. The pivots sit in columns 1 and 3, so columns 1 and 3 of A itself, (1, 2, 3, 0) and (0, 1, 1, 3), are a basis of \operatorname{Col} A. The columns of the reduced form would not do: they all end in two zeros. Both bases have two vectors, as they must.
A rank you can see
Find the rank of
describe \operatorname{Col} B, and decide whether B\mathbf{x} = (1, 3) and B\mathbf{x} = (4, 2) are consistent.
SolutionR_2 - \tfrac{1}{2}R_1 \to R_2 makes row 2 zero: \operatorname{rank} B = 1. The columns agree: (-4, -2) = -2(2, 1) and (6, 3) = 3(2, 1), so all three lie on the line y = \tfrac{1}{2}x through the origin, and that line is \operatorname{Col} B (figure above).
B\mathbf{x} = \mathbf{b} asks whether \mathbf{b} is a combination of the columns, that is, whether it lies on that line. (1, 3) does not. In rank terms, the same step turns \left[\begin{array}{ccc|c} 2 & -4 & 6 & 1 \\ 1 & -2 & 3 & 3 \end{array}\right] into one with second row 0 \; 0 \; 0 \mid \tfrac{5}{2}, so the augmented rank is 2 \ne 1: no solution. The point (4, 2) = 2(2, 1) is on the line, the augmented rank stays 1, and \mathbf{x} = (2, 0, 0) is one of infinitely many solutions.
Rank for every value of k
Find the rank of
for every real number k.
SolutionThe corner 1 does not depend on k, so use it: R_2 - 2R_1 \to R_2 and R_3 - 3R_1 \to R_3 give
Neither step divided by an expression in k, so this holds for every k.
- k \ne 2 and k \ne 3: pivots in all three rows, \operatorname{rank} M = 3.
- k = 2: row 2 is zero and row 3 is (0, 0, -1); a swap gives an echelon form with two nonzero rows, \operatorname{rank} M = 2.
- k = 3: row 2 is (0, 1, 0) and row 3 is zero, \operatorname{rank} M = 2.
The rank is never 1, since k - 2 and k - 3 cannot both be 0. By Determinants by cofactor expansion, \det M = (k - 2)(k - 3), nonzero exactly when the rank is 3 (The invertible matrix theorem).
Does a new blend add information?
Phalla proposes two new blends, \mathbf{p} = (4, 12, 1, 9) and \mathbf{q} = (1, 2, 0, 2). Added to Sokha’s notebook as a fifth row, which of them raises the rank?
SolutionA new row raises the rank exactly when it is not in the row space already there. From Example 1 the vectors of \operatorname{Row} A are
For \mathbf{p} the first and third entries force a = 4, b = 1, and then 3a = 12 and 2a + b = 9 match. So the rank stays 2. Since (0, 0, 1, 1) is blend 2 minus twice blend 1, \mathbf{p} = 2(\text{blend } 1) + \text{blend } 2.
Every vector of \operatorname{Row} A has second entry three times its first; \mathbf{q} has 2 \ne 3, so the rank rises to 3.
Every right-hand side, or at most one solution
Let
What does the rank say about C\mathbf{x} = \mathbf{b} and about C^{T}\mathbf{y} = \mathbf{d}? Find a \mathbf{d} for which the second has no solution.
SolutionR_3 - R_1 \to R_3 gives (0, 1, 2, 1), then R_3 - R_2 \to R_3 gives (0, 0, 1, 1): three nonzero echelon rows, \operatorname{rank} C = 3.
C is 3 \times 4 with rank 3 = m, so C\mathbf{x} = \mathbf{b} is consistent for every \mathbf{b} in \mathbb{R}^3, and since 3 < 4, each has infinitely many solutions, with 4 - 3 = 1 free variable.
C^{T} is 4 \times 3 with the same rank 3 = n, so a consistent C^{T}\mathbf{y} = \mathbf{d} has exactly one solution; but 3 < 4 = m, so some \mathbf{d} give none. Try \mathbf{d} = (0, 0, 0, 1), which must be a combination of the rows of C: a(1, 2, 0, 1) + b(0, 1, 1, 0) + c(1, 3, 2, 2). The first three entries give a + c = 0, 2a + b + 3c = 0, b + 2c = 0, so a = -c, then b = -c, then c = 0. All three are 0 and the last entry is 0, not 1: no solution.
Boundaries
- The rank counts pivots of the reduced form, but a basis of \operatorname{Col} A comes from the columns of A. Row operations keep the row space and the rank, and they can change the column space (Exercise 24).
- With a parameter, a step that divides by an expression such as k - 2 is valid only where it is nonzero, and the values where it vanishes are exactly where the rank can drop.
- Equal ranks do not mean equal spaces (Exercise 22).
- The count n - \operatorname{rank} A of free variables is a count here; reading it as a dimension is Rank and nullity.
Where this goes next
Rank and nullity turns the free-variable count into a theorem: the dimensions of the column space and of the solutions of A\mathbf{x} = \mathbf{0} (Kernel) add to n. Image reads \operatorname{Col} A as the outputs of \mathbf{x} \mapsto A\mathbf{x} (Multiplying a matrix by a vector). For a square n \times n matrix, rank n gives “every \mathbf{b}” and “at most one solution” at once, the core of The invertible matrix theorem and Finding an inverse by row reducing A next to I.
Exercises
Finding the rank
- Find the rank of \begin{bmatrix} 3 & -1 \\ -6 & 2 \end{bmatrix}.
- Find the rank of \begin{bmatrix} 1 & 2 & -1 \\ 0 & 1 & 4 \\ 2 & 5 & 2 \end{bmatrix}.
- Find the rank of \begin{bmatrix} 2 & 1 & 0 & 3 \\ 4 & 2 & 1 & 7 \\ -2 & -1 & 1 & -1 \end{bmatrix}.
- Find the rank of \begin{bmatrix} 1 & 4 \\ 2 & 3 \\ 0 & 5 \\ 3 & 2 \end{bmatrix}.
- Find the rank of \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 5 \\ 3 & 5 & 7 & 9 \end{bmatrix}.
- Vanna’s first three blends, over Brazilian, Colombian and Ethiopian beans, are (2, 1, 1), (1, 3, 2) and (3, 4, 3). Find the rank of the matrix with these rows and say what it means for the blends.
Row space and column space
- For the matrix of Exercise 3, give a basis of its row space and a basis of its column space.
- Is (1, 0, -9) in the row space of the matrix of Exercise 2? Is (1, 0, 5)?
- Phalla offers Vanna two more blends, (5, 5, 4) and (1, 1, 1). Added as a fourth row to the matrix of Exercise 6, which of them raises its rank?
- Describe the column space and the row space of the matrix of Exercise 1.
Rank with a parameter
- Find the rank of \begin{bmatrix} 1 & 2 \\ 3 & h \end{bmatrix} for every h.
- Find the rank of \begin{bmatrix} 1 & -1 & k \\ 2 & k - 4 & 4 \end{bmatrix} for every k.
- Find the rank of \begin{bmatrix} 1 & 0 & k \\ 0 & 1 & 1 \\ k & 1 & 2 \end{bmatrix} for every k.
Rank and systems
- A 3 \times 5 matrix A has rank 3. Is A\mathbf{x} = \mathbf{b} consistent for every \mathbf{b}? Can a solution be unique?
- A 5 \times 3 matrix A has rank 3. What are the solutions of A\mathbf{x} = \mathbf{0}? Is A\mathbf{x} = \mathbf{b} consistent for every \mathbf{b}?
- Let A = \begin{bmatrix} 1 & 2 & -1 \\ 2 & 4 & 1 \\ 3 & 6 & 0 \end{bmatrix}. Use ranks to decide whether A\mathbf{x} = (1, 5, 4) and A\mathbf{x} = (1, 5, 6) are consistent, and how many solutions each consistent one has.
- A system has 4 equations in 6 unknowns. Explain why it can never have exactly one solution.
- Find the rank of D = \begin{bmatrix} 1 & 0 & 2 \\ 0 & 1 & -1 \\ 1 & 1 & 1 \\ 2 & 1 & 3 \end{bmatrix} and of D^{T}, and give a basis of \operatorname{Col} D.
Reasoning
- Explain why the rank of an m \times n matrix is at most the smaller of m and n.
- Show that \operatorname{rank}(cA) = \operatorname{rank} A for every scalar c \ne 0. What happens when c = 0?
- Show that a matrix has rank 1 exactly when it equals \mathbf{u}\mathbf{v}^{T} for some nonzero column vectors \mathbf{u} in \mathbb{R}^m and \mathbf{v} in \mathbb{R}^n, that is, when column j is v_j\mathbf{u} for each j.
- Refute with a counterexample: “two matrices of the same size and the same rank have the same column space.”
- Explain why adding one row to a matrix raises its rank by at most 1. What does that say about one new blend at the roastery?
- Show with \begin{bmatrix} 1 & 1 \\ 3 & 3 \end{bmatrix} that a row operation can change the column space, and explain why no row operation can change the rank.
Answers
- \operatorname{rank} = 1. R_2 + 2R_1 \to R_2 makes row 2 zero.
- \operatorname{rank} = 2. R_3 - 2R_1 gives (0, 1, 4), equal to row 2, so R_3 - R_2 makes it zero.
- \operatorname{rank} = 3. R_2 - 2R_1 gives (0, 0, 1, 1), R_3 + R_1 gives (0, 0, 1, 2), and R_3 - R_2 gives (0, 0, 0, 1): three nonzero echelon rows.
- \operatorname{rank} = 2. R_2 - 2R_1 gives (0, -5), a second pivot, and there are only 2 columns.
- \operatorname{rank} = 2. R_2 - R_1 and R_3 - 2R_1 both give (0, 1, 2, 3) and R_4 - 3R_1 gives (0, 2, 4, 6); clearing with row 2 leaves two nonzero rows.
- \operatorname{rank} = 2. The third blend is the sum of the first two, so it adds no information; the first two are not multiples of each other.
- Row space: (2, 1, 0, 3), (0, 0, 1, 1), (0, 0, 0, 1), from Exercise 3. Pivots are in columns 1, 3, 4, so the column space has basis (2, 4, -2), (0, 1, 1), (3, 7, -1); with rank 3 it is all of \mathbb{R}^3.
- Yes: (1, 0, -9) = (1, 2, -1) - 2(0, 1, 4). No for (1, 0, 5): combinations of the echelon rows are (a, 2a + b, -a + 4b), the first two entries force a = 1, b = -2, and then -9 \ne 5.
- (5, 5, 4) = 2(2, 1, 1) + (1, 3, 2), so the rank stays 2. (1, 1, 1) raises it to 3: matching the first two entries needs a = \tfrac{2}{5}, b = \tfrac{1}{5}, giving third entry \tfrac{4}{5} \ne 1.
- The column space is the line through the origin and (3, -6), that is, y = -2x. The row space is the line through the origin and (3, -1).
- R_2 - 3R_1 gives (0, h - 6): rank 1 when h = 6, rank 2 otherwise.
- R_2 - 2R_1 gives (0, k - 2, 4 - 2k) = (k - 2)(0, 1, -2): rank 1 when k = 2, rank 2 otherwise.
- R_3 - kR_1 gives (0, 1, 2 - k^2), then R_3 - R_2 gives (0, 0, 1 - k^2): rank 2 when k = 1 or k = -1, rank 3 otherwise.
- Consistent for every \mathbf{b}, since the rank equals the number of rows. Never unique: every solution set has 5 - 3 = 2 free variables.
- Only \mathbf{x} = \mathbf{0}, since the rank equals the number of columns. Not every \mathbf{b}: the rank 3 is less than the 5 rows.
- \operatorname{rank} A = 2 (R_2 - 2R_1 and R_3 - 3R_1 both give (0, 0, 3)). For (1, 5, 4) the augmented rows become 0 \; 0 \; 3 \mid 3 and 0 \; 0 \; 3 \mid 1, augmented rank 3: no solution. For (1, 5, 6) both are 0 \; 0 \; 3 \mid 3, augmented rank 2: infinitely many solutions, with 3 - 2 = 1 free variable.
- The rank is at most 4 < 6, so a consistent system has at least 6 - 4 = 2 free variables: it has no solution or infinitely many.
- Both ranks are 2: row 3 is row 1 plus row 2, and row 4 is 2(\text{row } 1) + \text{row } 2. Pivots are in columns 1, 2, so \operatorname{Col} D has basis (1, 0, 1, 2), (0, 1, 1, 1); column 3 is 2(\text{column } 1) - \text{column } 2.
- Each pivot sits in its own row and its own column, so there are at most m and at most n.
- For c \ne 0, cA is A with every row scaled by c, a sequence of row operations, so the row space and rank are unchanged. For c = 0, cA is the zero matrix, of rank 0.
- If \operatorname{rank} A = 1, \operatorname{Col} A is a line spanned by some nonzero \mathbf{u}, so column j is v_j\mathbf{u} with not all v_j = 0: A = \mathbf{u}\mathbf{v}^{T}. Conversely, if A = \mathbf{u}\mathbf{v}^{T} with both nonzero, every column is a multiple of \mathbf{u} and some v_j\mathbf{u} is nonzero, so \operatorname{Col} A is a line: rank 1.
- \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} and \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} both have rank 1, but their column spaces are the x-axis and the y-axis.
- Either the new row is a combination of the old rows and the row space is unchanged, or it is not, and then a largest independent set of old rows plus the new row is independent and spans the new row space: one more dimension. One new blend adds at most one new piece of information.
- R_2 - 3R_1 \to R_2 gives \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}. The column space was the line through (1, 3) and is now the line through (1, 0). The rank is the dimension of the row space, which row operations keep, so the rank stays 1.