7.7 Minors, Rank and Cauchy–Binet

The determinant of a square matrix answers a yes-or-no question: is the matrix invertible? A rectangular matrix has no determinant, and a singular square matrix has determinant $0$ , which says nothing about how singular it is. Yet every matrix is full of square pieces, and each piece has a determinant. This section shows that these small determinants measure the rank exactly. It then answers a second question left open by multiplicativity: if $\mathbf{A}$ is $m \times n$ and $\mathbf{B}$ is $n \times m$ , the product $\mathbf{A}\mathbf{B}$ is square, so what is $\det(\mathbf{A}\mathbf{B})$ ? The answer, the Cauchy–Binet formula, is proved by the same multilinear expansion that gave uniqueness of the determinant in Theorem 7.4.2.

7.7.1. Submatrices and minors

In Definition 7.6.1 we deleted one row and one column of a square matrix and took the determinant of what was left. That is a special case of a more flexible operation: keep any $k$ rows and any $k$ columns. The recurring object is the square block sitting at the crossings of the chosen rows and columns, and it deserves a name.

A minor is the determinant of a square block cut out of a matrix by choosing some rows and the same number of columns.

For a positive integer $m$ , write $[m] = \{1, 2, \dots, m\}$ .

Definition 7.7.1 (Submatrix and Minor)

Let $\mathbf{A} = (a_{ij}) \in M_{m \times n}(F)$ , and let $1 \le k \le \min(m, n)$ . Let $I = \{i_1 < i_2 < \dots < i_k\} \subseteq [m]$ and $J = \{j_1 < j_2 < \dots < j_k\} \subseteq [n]$ be sets with exactly $k$ elements each, listed in increasing order. The submatrix of $\mathbf{A}$ on rows $I$ and columns $J$ is $\mathbf{A}_{I,J} \mathrel{:=} \big(a_{i_p j_q}\big)_{p, q = 1}^{k} \in M_k(F),$ the $k \times k$ matrix whose $(p, q)$ -entry is $a_{i_p j_q}$ . Its determinant $\det \mathbf{A}_{I,J}$ is a $k \times k$ minor of $\mathbf{A}$ .

In words: cross out every row not in $I$ and every column not in $J$ , and push the surviving entries together without changing their order. The chosen rows need not be adjacent, and neither need the columns. The sets $I$ and $J$ have the same size, so the block is square and has a determinant.

A $1 \times 1$ minor is a single entry, $\det \mathbf{A}_{\{i\},\{j\}} = a_{ij}$ . For a square $\mathbf{A} \in M_n(F)$ with $n \ge 2$ , the minor $M_{ij}$ of Definition 7.6.1 is the $(n - 1) \times (n - 1)$ minor with $I = [n] \setminus \{i\}$ and $J = [n] \setminus \{j\}$ . The only $n \times n$ minor of a square matrix is $\det \mathbf{A}$ itself. An $m \times n$ matrix has $\binom{m}{k}\binom{n}{k}$ minors of size $k$ , one for each choice of $I$ and $J$ .

Example. Let $\mathbf{A} = \begin{pmatrix} 1 & 2 & 0 \\ 0 & 1 & 3 \end{pmatrix} \in M_{2 \times 3}(\mathbb{Q}).$ Its $2 \times 2$ minors all use $I = \{1, 2\}$ , and there are three choices of $J$ : $\begin{aligned} \det \mathbf{A}_{I,\{1,2\}} &= \det\begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix} = 1, \\ \det \mathbf{A}_{I,\{1,3\}} &= \det\begin{pmatrix} 1 & 0 \\ 0 & 3 \end{pmatrix} = 3, \\ \det \mathbf{A}_{I,\{2,3\}} &= \det\begin{pmatrix} 2 & 0 \\ 1 & 3 \end{pmatrix} = 6. \end{aligned}$ Its six $1 \times 1$ minors are its entries. It has no $3 \times 3$ minors, since it has only two rows.

A degenerate example. Every minor of the zero matrix $0_{m \times n}$ is $0$ : each block is a zero matrix, whose determinant is $0$ by Theorem 7.4.6. This case matters because it is exactly the matrix of rank $0$ , and the theorem below has to treat it separately.

Non-example by minimal change. Take the same rows and columns but list the columns of $\mathbf{A}$ above in the order $3, 1$ : the block $\begin{pmatrix} 0 & 1 \\ 3 & 0 \end{pmatrix}$ has determinant $-3$ , not $3$ . Every entry is still an entry of $\mathbf{A}$ from rows $\{1, 2\}$ and columns $\{1, 3\}$ ; what fails is the clause listed in increasing order. Reordering columns changes the determinant by a sign (Theorem 7.2.1), so the order convention is what makes “the” minor on $(I, J)$ a single well-defined number.

Why this definition. Insisting on increasing order costs nothing and removes all sign ambiguity. Insisting on $|I| = |J|$ is forced: only square blocks have determinants.

Warning. Rank is not read off principal minors. A principal minor uses the same index set for rows and columns ( $I = J$ ). It is tempting to test rank using only these, but they can all vanish for a non-zero matrix. For $\mathbf{N} = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$ , the principal minors are $0$ , $0$ and $\det \mathbf{N} = 0$ , yet $\operatorname{rank} \mathbf{N} = 1$ . The non-zero minor is the off-diagonal entry $\det \mathbf{N}_{\{1\},\{2\}} = 1$ . The theorem below uses all minors.

Quick check. How many $2 \times 2$ minors does a $3 \times 4$ matrix have? How many $3 \times 3$ minors?

Solution. A $2 \times 2$ minor needs $2$ of the $3$ rows and $2$ of the $4$ columns: $\binom{3}{2}\binom{4}{2} = 3 \cdot 6 = 18$ . A $3 \times 3$ minor uses all three rows and $3$ of the $4$ columns: $\binom{3}{3}\binom{4}{3} = 4$ .

7.7.2. Rank via minors

A non-zero determinant of a square block means the block is invertible, so its columns are independent. Independent columns inside a block come from independent columns of the whole matrix. So a large non-zero minor forces large rank. The converse, that large rank produces a large non-zero minor, needs us to find the right rows as well as the right columns. Both directions together give a description of rank using only determinants:

Theorem 7.7.1 (Rank via Minors)

Let $\mathbf{A} \in M_{m \times n}(F)$ be non-zero.

(a) $\operatorname{rank} \mathbf{A}$ is the largest integer $k$ such that $\mathbf{A}$ has a non-zero $k \times k$ minor.
(b) Equivalently, for each $1 \le k \le \min(m, n)$ : $\operatorname{rank} \mathbf{A} \ge k$ if and only if some $k \times k$ minor of $\mathbf{A}$ is non-zero; and $\operatorname{rank} \mathbf{A} < k$ if and only if every $k \times k$ minor of $\mathbf{A}$ is zero.

Idea. Two inequalities. ① A non-zero $k \times k$ minor on rows $I$ and columns $J$ makes $\mathbf{A}_{I,J}$ invertible; a dependence among the columns of $\mathbf{A}$ indexed by $J$ would restrict to a dependence among the columns of $\mathbf{A}_{I,J}$ . So $\operatorname{rank} \mathbf{A} \ge k$ . ② If $\operatorname{rank} \mathbf{A} = r$ , choose $r$ independent columns (pivot columns). The $m \times r$ matrix they form has rank $r$ , so by row rank = column rank it has $r$ independent rows. Those rows cut out an $r \times r$ block with independent rows, hence a non-zero determinant.

Proof. Step 1: a non-zero $k \times k$ minor forces $\operatorname{rank} \mathbf{A} \ge k$ . Let $I = \{i_1 < \dots < i_k\}$ and $J = \{j_1 < \dots < j_k\}$ with $\det \mathbf{A}_{I,J} \ne 0$ . Write $\mathbf{a}_1, \dots, \mathbf{a}_n$ for the columns of $\mathbf{A}$ . Suppose $c_1\mathbf{a}_{j_1} + \dots + c_k\mathbf{a}_{j_k} = \mathbf{0}$ with $c_1, \dots, c_k \in F$ . Reading only the entries in rows $i_1, \dots, i_k$ of this vector equation gives $\sum_{q} c_q\, a_{i_p j_q} = 0$ for $p = 1, \dots, k$ , that is, $\mathbf{A}_{I,J}\mathbf{c} = \mathbf{0}$ with $\mathbf{c} = (c_1, \dots, c_k)$ . By Theorem 7.5.2, $\mathbf{A}_{I,J}$ is invertible, so $\mathbf{c} = \mathbf{0}$ by Theorem 3.4.4. Hence $(\mathbf{a}_{j_1}, \dots, \mathbf{a}_{j_k})$ is a linearly independent list in $\operatorname{col}(\mathbf{A})$ , and by Theorem 1.6.3 (a), $k \le \dim\operatorname{col}(\mathbf{A}) = \operatorname{rank} \mathbf{A}$ .

Step 2: $\mathbf{A}$ has a non-zero $r \times r$ minor, where $r = \operatorname{rank} \mathbf{A}$ . Since $\mathbf{A} \ne 0$ , some column is non-zero, so $r \ge 1$ . By Theorem 3.5.2 (a), the pivot columns $\mathbf{a}_{j_1}, \dots, \mathbf{a}_{j_r}$ ( $j_1 < \dots < j_r$ ) are linearly independent. Let $J = \{j_1, \dots, j_r\}$ and let $\mathbf{A}' = \mathbf{A}_{[m],J} \in M_{m \times r}(F)$ be the matrix with these columns. By Theorem 3.5.10 (a), $\operatorname{rank} \mathbf{A}' = r$ , so by Theorem 3.5.5 the row space of $\mathbf{A}'$ has dimension $r$ . The $m$ rows of $\mathbf{A}'$ span its row space, so by Theorem 1.5.4 some $r$ of them, in rows $i_1 < \dots < i_r$ , form a basis of it; in particular they are linearly independent. These are exactly the rows of $\mathbf{B} = \mathbf{A}_{I,J} \in M_r(F)$ , where $I = \{i_1, \dots, i_r\}$ . Transposition is a linear bijection from $1 \times r$ rows to columns in $F^r$ , so the columns of $\mathbf{B}^{\top}$ are linearly independent. By Theorem 3.4.4, $\mathbf{B}^{\top}$ is invertible, so $\det \mathbf{B}^{\top} \ne 0$ by Theorem 7.5.2, and $\det \mathbf{B} = \det \mathbf{B}^{\top} \ne 0$ by Theorem 7.4.5.

Conclusion. By Step 2 there is a non-zero minor of size $r$ , and by Step 1 there is none of size larger than $r$ . This proves (a). For (b): if $\operatorname{rank} \mathbf{A} \ge k$ , then Step 2 gives a non-zero $r \times r$ minor with $r \ge k$ , and we still need one of size exactly $k$ . Expanding that $r \times r$ determinant along any row (Theorem 7.6.1) writes it as a combination of $(r-1) \times (r-1)$ minors of the block, each of which is also an $(r-1) \times (r-1)$ minor of $\mathbf{A}$ ; since the determinant is non-zero, one of these minors is non-zero. Repeating $r - k$ times gives a non-zero $k \times k$ minor. Conversely, a non-zero $k \times k$ minor gives $\operatorname{rank} \mathbf{A} \ge k$ by Step 1. The second equivalence in (b) is the negation of the first.

The theorem turns “rank at most $k - 1$ ” into a finite list of polynomial equations in the entries: all $k \times k$ minors vanish. That is why rank can only drop when the entries satisfy special equations, as the next example shows.

Example (Rank of a Family of Matrices)

For $t \in \mathbb{Q}$ , let $\mathbf{A}(t) = \begin{pmatrix} 1 & 2 & 1 \\ 2 & t & 3 \\ 3 & 6 & t \end{pmatrix}.$ Find $\operatorname{rank} \mathbf{A}(t)$ for every $t$ .

Solution. The only $3 \times 3$ minor is $\det \mathbf{A}(t)$ . By cofactor expansion along the first row (Theorem 7.6.1), $\begin{aligned} \det \mathbf{A}(t) &= 1\cdot(t^2 - 18) - 2\cdot(2t - 9) + 1\cdot(12 - 3t) \\ &= t^2 - 7t + 12 = (t - 3)(t - 4). \end{aligned}$ So for $t \ne 3, 4$ , $\mathbf{A}(t)$ has a non-zero $3 \times 3$ minor and $\operatorname{rank} \mathbf{A}(t) = 3$ by Theorem 7.7.1.

For $t \in \{3, 4\}$ every $3 \times 3$ minor is zero, so $\operatorname{rank} \mathbf{A}(t) \le 2$ . Look for a $2 \times 2$ minor that does not involve $t$ : rows $\{1, 2\}$ and columns $\{1, 3\}$ give $\det\begin{pmatrix} 1 & 1 \\ 2 & 3 \end{pmatrix} = 1 \ne 0 .$ Hence $\operatorname{rank} \mathbf{A}(3) = \operatorname{rank} \mathbf{A}(4) = 2$ . The same minor shows $\operatorname{rank} \mathbf{A}(t) \ge 2$ for every $t$ , so rank $1$ never occurs.

Remark. To compute the rank of one given matrix, elimination is far cheaper: a $10 \times 10$ matrix has $\binom{10}{5}^2 = 63504$ minors of size $5$ . Minors earn their keep in theory. They show that rank is unchanged by transposing (the minors of $\mathbf{A}^{\top}$ are the minors of $\mathbf{A}$ , by Theorem 7.4.5) and by enlarging the field (Exercise (C2: Rank does not depend on the field)), and they describe the matrices of rank below $k$ by polynomial equations.

7.7.3. The Cauchy–Binet formula

Multiplicativity, Theorem 7.5.4, handles $\det(\mathbf{A}\mathbf{B})$ when both factors are square. Now let $\mathbf{A} \in M_{m \times n}(F)$ and $\mathbf{B} \in M_{n \times m}(F)$ . The product $\mathbf{A}\mathbf{B}$ is $m \times m$ , so it has a determinant, but $\det \mathbf{A}$ and $\det \mathbf{B}$ do not exist. The natural candidates to replace them are the largest minors: the $m \times m$ minors of $\mathbf{A}$ , which keep all rows and choose $m$ columns $S$ , and the $m \times m$ minors of $\mathbf{B}$ , which keep all columns and choose the same $m$ rows $S$ .

Theorem 7.7.2 (Cauchy–Binet Formula)

Let $\mathbf{A} \in M_{m \times n}(F)$ and $\mathbf{B} \in M_{n \times m}(F)$ . Then $\det(\mathbf{A}\mathbf{B}) = \sum_{\substack{S \subseteq [n] \\ |S| = m}} \det \mathbf{A}_{[m],S}\, \det \mathbf{B}_{S,[m]} ,$ the sum running over all $m$ -element subsets $S$ of $[n]$ . In particular:

(a) if $m > n$ , the sum is empty and $\det(\mathbf{A}\mathbf{B}) = 0$ ;
(b) if $m = n$ , the only subset is $S = [n]$ and the formula is $\det(\mathbf{A}\mathbf{B}) = \det \mathbf{A} \det \mathbf{B}$ .

Idea. Treat $\det$ as a function of the $m$ columns of $\mathbf{A}\mathbf{B}$ . Column $k$ of $\mathbf{A}\mathbf{B}$ is $\mathbf{A}\mathbf{b}_k = \sum_j b_{jk}\mathbf{a}_j$ , a combination of the columns of $\mathbf{A}$ . Expand by multilinearity in all $m$ columns at once, exactly as in the uniqueness proof: one term for each way of picking a column $\mathbf{a}_{\varphi(k)}$ of $\mathbf{A}$ in slot $k$ . ① Terms that pick the same column twice vanish, because the determinant is alternating. ② The surviving picks use $m$ distinct columns, forming a set $S$ , in some order; putting them in increasing order costs the sign of the reordering (Lemma 7.4.1). ③ Collecting all orders of the same $S$ produces a Leibniz sum, which is $\det \mathbf{B}_{S,[m]}$ .

Proof. Write $\mathbf{a}_1, \dots, \mathbf{a}_n \in F^m$ for the columns of $\mathbf{A}$ and $b_{jk}$ for the entries of $\mathbf{B}$ . For $\mathbf{x}_1, \dots, \mathbf{x}_m \in F^m$ , the function $D(\mathbf{x}_1, \dots, \mathbf{x}_m) = \det(\mathbf{x}_1, \dots, \mathbf{x}_m)$ is an alternating $m$ -linear form by Theorem 7.4.3.

By Theorem 0.9.2, column $k$ of $\mathbf{A}\mathbf{B}$ is $\mathbf{A}\mathbf{b}_k = \sum_{j=1}^{n} b_{jk}\mathbf{a}_j$ . Expanding $D$ by linearity in each of its $m$ arguments in turn, $\det(\mathbf{A}\mathbf{B}) = D\Big(\sum_{j=1}^{n} b_{j1}\mathbf{a}_j, \dots, \sum_{j=1}^{n} b_{jm}\mathbf{a}_j\Big) = \sum_{\varphi} \Big(\prod_{k=1}^{m} b_{\varphi(k)k}\Big)\, D(\mathbf{a}_{\varphi(1)}, \dots, \mathbf{a}_{\varphi(m)}),$ where $\varphi$ runs over all functions $[m] \to [n]$ . If $\varphi$ is not injective, two arguments of $D$ are equal and the term is $0$ because $D$ is alternating (Definition 7.2.2). So only injective $\varphi$ contribute. In particular, if $m > n$ there is no injective $\varphi$ , and $\det(\mathbf{A}\mathbf{B}) = 0$ , which proves (a).

An injective $\varphi$ has an image $S = \{s_1 < \dots < s_m\} \subseteq [n]$ with $m$ elements, and then $\varphi(k) = s_{\pi(k)}$ for exactly one $\pi \in S_m$ . Conversely each pair $(S, \pi)$ gives an injective $\varphi$ . By Lemma 7.4.1 with $\mathbf{v}_p = \mathbf{a}_{s_p}$ , $D(\mathbf{a}_{\varphi(1)}, \dots, \mathbf{a}_{\varphi(m)}) = \operatorname{sgn}(\pi)\, D(\mathbf{a}_{s_1}, \dots, \mathbf{a}_{s_m}) = \operatorname{sgn}(\pi)\, \det \mathbf{A}_{[m],S},$ since $\mathbf{A}_{[m],S}$ has columns $\mathbf{a}_{s_1}, \dots, \mathbf{a}_{s_m}$ . Hence $\det(\mathbf{A}\mathbf{B}) = \sum_{|S| = m} \det \mathbf{A}_{[m],S} \sum_{\pi \in S_m} \operatorname{sgn}(\pi) \prod_{k=1}^{m} b_{s_{\pi(k)}k} .$ The matrix $\mathbf{B}_{S,[m]}$ has $(p, k)$ -entry $b_{s_p k}$ , so its $(\pi(k), k)$ -entry is $b_{s_{\pi(k)}k}$ , and the inner sum is $\det \mathbf{B}_{S,[m]}$ by Definition 7.4.1. This proves the formula. For $m = n$ , the only $S$ is $[n]$ , with $\mathbf{A}_{[n],[n]} = \mathbf{A}$ and $\mathbf{B}_{[n],[n]} = \mathbf{B}$ , which gives (b).

Part (b) is a second proof of multiplicativity, and part (a) matches what rank predicts: if $m > n$ , then $\operatorname{rank}(\mathbf{A}\mathbf{B}) \le \operatorname{rank} \mathbf{A} \le n < m$ by Theorem 3.5.9, so $\mathbf{A}\mathbf{B}$ is not invertible. The formula also passes a sanity check at $m = 1$ : a $1 \times n$ row times an $n \times 1$ column is the $1 \times 1$ matrix $\sum_j a_{1j}b_{j1}$ , and the $1 \times 1$ minors are single entries.

Remark. The proof uses only sums, differences and products of entries, together with Lemma 7.4.1, which is division-free by the remark in §4. So, like the results flagged in §4–§6, the Cauchy–Binet formula holds for matrices with entries in any commutative ring.

Example (Cauchy–Binet for a

2 \times 3

times

3 \times 2

Product)

Let $\mathbf{A} = \begin{pmatrix} 1 & 2 & 0 \\ 0 & 1 & 3 \end{pmatrix}, \qquad \mathbf{B} = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 2 & -1 \end{pmatrix}$ over $\mathbb{Q}$ . Compute $\det(\mathbf{A}\mathbf{B})$ directly and by the Cauchy–Binet formula. Then compute $\det(\mathbf{B}\mathbf{A})$ .

Solution. Directly. $\mathbf{A}\mathbf{B} = \begin{pmatrix} 1 + 2 + 0 & 0 + 2 + 0 \\ 0 + 1 + 6 & 0 + 1 - 3 \end{pmatrix} = \begin{pmatrix} 3 & 2 \\ 7 & -2 \end{pmatrix}$ , so $\det(\mathbf{A}\mathbf{B}) = -6 - 14 = -20$ .

By Cauchy–Binet. Here $m = 2$ , $n = 3$ , and there are three subsets $S$ . The minors of $\mathbf{A}$ were computed after Definition 7.7.1. The minors of $\mathbf{B}$ keep both columns and rows $S$ :

$S$	$\det \mathbf{A}_{[2],S}$	$\det \mathbf{B}_{S,[2]}$	product
$\{1, 2\}$	$1$	$\det\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} = 1$	$1$
$\{1, 3\}$	$3$	$\det\begin{pmatrix} 1 & 0 \\ 2 & -1 \end{pmatrix} = -1$	$-3$
$\{2, 3\}$	$6$	$\det\begin{pmatrix} 1 & 1 \\ 2 & -1 \end{pmatrix} = -3$	$-18$

The sum is $1 - 3 - 18 = -20$ , in agreement.

The other product. $\mathbf{B}\mathbf{A}$ is $3 \times 3$ , and here the roles are $m = 3 > n = 2$ , so $\det(\mathbf{B}\mathbf{A}) = 0$ by Theorem 7.7.2 (a). Indeed $\mathbf{B}\mathbf{A} = \begin{pmatrix} 1 & 2 & 0 \\ 1 & 3 & 3 \\ 2 & 3 & -3 \end{pmatrix}$ , whose third row is $3$ times the first minus the second, so $\det(\mathbf{B}\mathbf{A}) = 0$ .

Warning. For non-square factors, $\det(\mathbf{A}\mathbf{B})$ and $\det(\mathbf{B}\mathbf{A})$ differ. For square matrices $\det(\mathbf{A}\mathbf{B}) = \det \mathbf{A}\det \mathbf{B} = \det(\mathbf{B}\mathbf{A})$ . In the example above, $\det(\mathbf{A}\mathbf{B}) = -20$ while $\det(\mathbf{B}\mathbf{A}) = 0$ . An even smaller case: $\mathbf{A} = \begin{pmatrix} 1 & 1 \end{pmatrix}$ and $\mathbf{B} = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$ give $\mathbf{A}\mathbf{B} = (2)$ and $\mathbf{B}\mathbf{A} = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ , with determinants $2$ and $0$ . Also, do not write “ $\det \mathbf{A} \det \mathbf{B}$ ” for non-square $\mathbf{A}$ , $\mathbf{B}$ : those symbols are undefined, and the sum over $S$ is what replaces them.

Quick check. Let $\mathbf{u}, \mathbf{v} \in F^n$ with $n \ge 2$ . Without computing, what is $\det(\mathbf{u}\mathbf{v}^{\top})$ ?

Solution. $\mathbf{u}\mathbf{v}^{\top}$ is the product of the $n \times 1$ matrix $\mathbf{u}$ and the $1 \times n$ matrix $\mathbf{v}^{\top}$ . Here the product is $n \times n$ and the middle size is $1 < n$ , so $\det(\mathbf{u}\mathbf{v}^{\top}) = 0$ by Theorem 7.7.2 (a).

7.7.4. Sums of squares over the reals

Over $\mathbb{R}$ , take $\mathbf{B} = \mathbf{A}^{\top}$ . The minors of $\mathbf{A}^{\top}$ are the minors of $\mathbf{A}$ with rows and columns exchanged, so Cauchy–Binet writes $\det(\mathbf{A}\mathbf{A}^{\top})$ as a sum of squares.

Corollary 7.7.3 (Gram Determinants Are Non-negative)

Let $\mathbf{A} \in M_{m \times n}(\mathbb{R})$ . Then $\det(\mathbf{A}\mathbf{A}^{\top}) = \sum_{\substack{S \subseteq [n] \\ |S| = m}} \big(\det \mathbf{A}_{[m],S}\big)^2 \ \ge\ 0,$ with equality if and only if $\operatorname{rank} \mathbf{A} < m$ .

Proof. By Definition 0.9.10, the $(p, k)$ -entry of $(\mathbf{A}^{\top})_{S,[m]}$ is the $(k, s_p)$ -entry of $\mathbf{A}$ , so $(\mathbf{A}^{\top})_{S,[m]} = (\mathbf{A}_{[m],S})^{\top}$ . By Theorem 7.4.5, $\det (\mathbf{A}^{\top})_{S,[m]} = \det \mathbf{A}_{[m],S}$ . Substituting into Theorem 7.7.2 with $\mathbf{B} = \mathbf{A}^{\top}$ gives the formula. A sum of squares of real numbers is $\ge 0$ , and it is $0$ if and only if every term is $0$ . Every $m \times m$ minor of $\mathbf{A}$ has the form $\det \mathbf{A}_{[m],S}$ , since an $m \times m$ minor must use all $m$ rows. If $m > n$ , the sum is empty and $\operatorname{rank} \mathbf{A} \le n < m$ . Otherwise, by Theorem 7.7.1 (b) (or directly if $\mathbf{A} = 0$ ), all these minors vanish if and only if $\operatorname{rank} \mathbf{A} < m$ .

The matrix $\mathbf{A}\mathbf{A}^{\top}$ collects the dot products of the rows of $\mathbf{A}$ with each other. Such matrices of pairwise inner products are Gram matrices; Chapters 11 and 13 study them, and there this corollary becomes the statement that a Gram matrix is positive semidefinite. For $m = 2$ the corollary is a classical identity about two vectors, Exercise (B3: The Lagrange identity). Over $\mathbb{C}$ or $\mathbb{F}_p$ the conclusion “ $\ge 0$ ” has no meaning, and the equality case can fail: over $\mathbb{C}$ , $\mathbf{A} = \begin{pmatrix} 1 & i \end{pmatrix}$ has rank $1$ but $\mathbf{A}\mathbf{A}^{\top} = (1 + i^2) = (0)$ .

7.7.5. Exercises

A. Check your understanding

Exercise (A1)

(a) Define the $k \times k$ minor of $\mathbf{A} \in M_{m \times n}(F)$ on rows $I$ and columns $J$ .
(b) True or false: if every principal minor of a square matrix is zero, the matrix is zero. Justify your answer.
(c) True or false: if $\mathbf{A} \in M_{4 \times 5}(F)$ has a non-zero $3 \times 3$ minor, then $\operatorname{rank} \mathbf{A} \ge 3$ . Justify your answer.
(d) True or false: if $\mathbf{A} \in M_{3}(F)$ has a zero $2 \times 2$ minor, then $\operatorname{rank} \mathbf{A} \le 1$ . Justify your answer.
(e) State the Cauchy–Binet formula, and say what it gives when $m > n$ .
(f) Let $\mathbf{A} \in M_{2 \times 3}(\mathbb{R})$ . Why is $\det(\mathbf{A}^{\top} \mathbf{A}) = 0$ ?

Solution.

(a) For $I = \{i_1 < \dots < i_k\} \subseteq [m]$ and $J = \{j_1 < \dots < j_k\} \subseteq [n]$ , it is $\det \mathbf{A}_{I,J}$ , where $\mathbf{A}_{I,J} \in M_k(F)$ has $(p, q)$ -entry $a_{i_pj_q}$ (Definition 7.7.1).
(b) False. $\mathbf{N} = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$ has principal minors $0, 0, 0$ but $\mathbf{N} \ne 0$ .
(c) True, by Step 1 of the proof of Theorem 7.7.1, or by part (b) of that theorem.
(d) False. The rank is decided by whether some minor is non-zero, not by one zero minor. $\mathbf{I}_3$ has the zero $2 \times 2$ minor on rows $\{1, 2\}$ and columns $\{2, 3\}$ , namely $\det\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} = 0$ , but $\operatorname{rank} \mathbf{I}_3 = 3$ .
(e) For $\mathbf{A} \in M_{m \times n}(F)$ and $\mathbf{B} \in M_{n \times m}(F)$ , $\det(\mathbf{A}\mathbf{B}) = \sum_{|S| = m} \det \mathbf{A}_{[m],S}\det \mathbf{B}_{S,[m]}$ , summed over $m$ -subsets $S \subseteq [n]$ . If $m > n$ there are no such subsets and $\det(\mathbf{A}\mathbf{B}) = 0$ .
(f) $\mathbf{A}^{\top} \mathbf{A}$ is $3 \times 3$ , the product of a $3 \times 2$ and a $2 \times 3$ matrix. By Theorem 7.7.2 (a) with $m = 3 > n = 2$ , $\det(\mathbf{A}^{\top} \mathbf{A}) = 0$ .

B. Practice

Exercise (B1: Rank with a parameter)

For $s \in \mathbb{Q}$ , let $\mathbf{A}(s) = \begin{pmatrix} 1 & s & 1 \\ s & 1 & 1 \\ 1 & 1 & s \end{pmatrix}$ . Use minors to find $\operatorname{rank} \mathbf{A}(s)$ for every $s$ .

Solution. By cofactor expansion along the first row (Theorem 7.6.1), $\begin{aligned} \det \mathbf{A}(s) &= 1\cdot(s - 1) - s\,(s^2 - 1) + 1\cdot(s - 1) \\ &= -s^3 + 3s - 2 = -(s - 1)^2(s + 2). \end{aligned}$ If $s \ne 1, -2$ , this $3 \times 3$ minor is non-zero, so $\operatorname{rank} \mathbf{A}(s) = 3$ by Theorem 7.7.1.

If $s = -2$ , then $\det \mathbf{A}(-2) = 0$ , so $\operatorname{rank} \mathbf{A}(-2) \le 2$ . The minor on rows $\{1, 2\}$ and columns $\{1, 2\}$ is $\det\begin{pmatrix} 1 & -2 \\ -2 & 1 \end{pmatrix} = 1 - 4 = -3 \ne 0$ . Hence $\operatorname{rank} \mathbf{A}(-2) = 2$ .

If $s = 1$ , every entry is $1$ . Every $2 \times 2$ minor is $\det\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} = 0$ , and the $1 \times 1$ minors are non-zero. Hence $\operatorname{rank} \mathbf{A}(1) = 1$ .

Exercise (B2: Checking Cauchy–Binet)

Let $\mathbf{A} = \begin{pmatrix} 1 & 0 & 2 \\ -1 & 1 & 1 \end{pmatrix}$ and $\mathbf{B} = \begin{pmatrix} 2 & 1 \\ 0 & 1 \\ 1 & -1 \end{pmatrix}$ over $\mathbb{Q}$ .

(a) Compute $\det(\mathbf{A}\mathbf{B})$ directly.
(b) Compute $\det(\mathbf{A}\mathbf{B})$ by the Cauchy–Binet formula.
(c) Hence, without multiplying, find $\det(\mathbf{B}\mathbf{A})$ .

Solution.

(a) $\mathbf{A}\mathbf{B} = \begin{pmatrix} 2 + 0 + 2 & 1 + 0 - 2 \\ -2 + 0 + 1 & -1 + 1 - 1 \end{pmatrix} = \begin{pmatrix} 4 & -1 \\ -1 & -1 \end{pmatrix}$ , so $\det(\mathbf{A}\mathbf{B}) = -4 - 1 = -5$ .
(b) The three subsets of $[3]$ of size $2$ give $\begin{aligned} S = \{1, 2\}&: \ \det\begin{pmatrix} 1 & 0 \\ -1 & 1 \end{pmatrix}\det\begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix} = 1 \cdot 2 = 2, \\ S = \{1, 3\}&: \ \det\begin{pmatrix} 1 & 2 \\ -1 & 1 \end{pmatrix}\det\begin{pmatrix} 2 & 1 \\ 1 & -1 \end{pmatrix} = 3 \cdot (-3) = -9, \\ S = \{2, 3\}&: \ \det\begin{pmatrix} 0 & 2 \\ 1 & 1 \end{pmatrix}\det\begin{pmatrix} 0 & 1 \\ 1 & -1 \end{pmatrix} = (-2)(-1) = 2 . \end{aligned}$ The sum is $2 - 9 + 2 = -5$ , agreeing with (a).
(c) $\mathbf{B}\mathbf{A} \in M_3(\mathbb{Q})$ is a product through $F^2$ , so $\det(\mathbf{B}\mathbf{A}) = 0$ by Theorem 7.7.2 (a).

Exercise (B3: The Lagrange identity)

Let $\mathbf{a} = (a_1, \dots, a_n)$ and $\mathbf{b} = (b_1, \dots, b_n)$ be vectors in $\mathbb{R}^n$ , $n \ge 2$ , and write $\mathbf{a} \cdot \mathbf{b} = \sum_i a_ib_i$ .

(a) Let $\mathbf{M} \in M_{2 \times n}(\mathbb{R})$ have rows $\mathbf{a}^{\top}$ and $\mathbf{b}^{\top}$ . Compute $\mathbf{M}\mathbf{M}^{\top}$ .
(b) Hence prove the Lagrange identity $(\mathbf{a} \cdot \mathbf{a})(\mathbf{b} \cdot \mathbf{b}) - (\mathbf{a} \cdot \mathbf{b})^2 = \sum_{1 \le i < j \le n} (a_ib_j - a_jb_i)^2 .$
(c) Check it for $\mathbf{a} = (1, 2, 3)$ and $\mathbf{b} = (4, 5, 6)$ , and deduce $(\mathbf{a} \cdot \mathbf{b})^2 \le (\mathbf{a} \cdot \mathbf{a})(\mathbf{b} \cdot \mathbf{b})$ for all $\mathbf{a}, \mathbf{b} \in \mathbb{R}^n$ .

Solution.

(a) By Theorem 0.9.2, the $(p, q)$ -entry of $\mathbf{M}\mathbf{M}^{\top}$ is row $p$ of $\mathbf{M}$ times column $q$ of $\mathbf{M}^{\top}$ , which is row $q$ of $\mathbf{M}$ transposed. Hence $\mathbf{M}\mathbf{M}^{\top} = \begin{pmatrix} \mathbf{a} \cdot \mathbf{a} & \mathbf{a} \cdot \mathbf{b} \\ \mathbf{b} \cdot \mathbf{a} & \mathbf{b} \cdot \mathbf{b} \end{pmatrix}, \qquad \mathbf{b} \cdot \mathbf{a} = \mathbf{a} \cdot \mathbf{b} .$
(b) The left side of the identity is $\det(\mathbf{M}\mathbf{M}^{\top})$ . By Corollary 7.7.3 with $m = 2$ , it equals the sum over $S = \{i < j\}$ of $(\det \mathbf{M}_{[2],S})^2$ , and $\mathbf{M}_{[2],\{i,j\}} = \begin{pmatrix} a_i & a_j \\ b_i & b_j \end{pmatrix}$ has determinant $a_ib_j - a_jb_i$ . This proves the identity.
(c) Left side: $\mathbf{a} \cdot \mathbf{a} = 14$ , $\mathbf{b} \cdot \mathbf{b} = 77$ , $\mathbf{a} \cdot \mathbf{b} = 32$ , so $14 \cdot 77 - 32^2 = 1078 - 1024 = 54$ . Right side: the pairs $(1,2), (1,3), (2,3)$ give $5 - 8 = -3$ , $6 - 12 = -6$ , $12 - 15 = -3$ , and $9 + 36 + 9 = 54$ . In general the right side is a sum of squares of reals, hence $\ge 0$ , so $(\mathbf{a} \cdot \mathbf{b})^2 \le (\mathbf{a} \cdot \mathbf{a})(\mathbf{b} \cdot \mathbf{b})$ .

C. Going deeper

Exercise (C1: Counting spanning trees)

Consider the network with vertices $1, 2, 3, 4$ and five edges, oriented as $e_1 = 1 \to 2$ , $e_2 = 2 \to 3$ , $e_3 = 3 \to 4$ , $e_4 = 4 \to 1$ , $e_5 = 1 \to 3$ . A spanning tree is a set of $3$ edges that connects all four vertices (ignoring orientation). Let $\mathbf{N} \in M_{4 \times 5}(\mathbb{R})$ be its incidence matrix (Definition 3.7.1), let $\mathbf{L} = \mathbf{N}\mathbf{N}^{\top}$ , and let $\mathbf{N}_0$ and $\mathbf{L}_0$ be $\mathbf{N}$ and $\mathbf{L}$ with the row (and, for $\mathbf{L}$ , the column) of vertex $4$ deleted.

(a) Compute $\mathbf{L}$ and $\det \mathbf{L}_0$ .
(b) List the spanning trees and count them.
(c) Show that $\mathbf{L}_0 = \mathbf{N}_0\mathbf{N}_0^{\top}$ , and use Corollary 7.7.3 to write $\det \mathbf{L}_0$ as a sum over $3$ -element sets of edges.
(d) Compute the minor of $\mathbf{N}_0$ for the tree $\{e_1, e_2, e_3\}$ and for the non-tree $\{e_1, e_2, e_5\}$ . Explain, for these two sets, why the answers are $\pm 1$ and $0$ .

The matrix-tree theorem says that for every connected network, $\det \mathbf{L}_0$ equals the number of spanning trees; parts (c) and (d) are the heart of its proof, which Chapter 24 completes.

Hint: for (d), a set of edges containing a cycle gives dependent columns.

Solution.

(a) Column $e$ of $\mathbf{N}$ has $1$ at the tail and $-1$ at the head: $\mathbf{N} = \begin{pmatrix} 1 & 0 & 0 & -1 & 1 \\ -1 & 1 & 0 & 0 & 0 \\ 0 & -1 & 1 & 0 & -1 \\ 0 & 0 & -1 & 1 & 0 \end{pmatrix}, \qquad \mathbf{L} = \mathbf{N}\mathbf{N}^{\top} = \begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 2 & -1 & 0 \\ -1 & -1 & 3 & -1 \\ -1 & 0 & -1 & 2 \end{pmatrix}.$ (Diagonal entries count the edges at a vertex; off-diagonal entries are $-1$ for each edge joining two vertices.) Expanding along the first row, $\begin{aligned} \det \mathbf{L}_0 &= \det\begin{pmatrix} 3 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 3 \end{pmatrix} \\ &= 3(6 - 1) + 1\cdot(-3 - 1) - 1\cdot(1 + 2) = 15 - 4 - 3 = 8 . \end{aligned}$
(b) There are $\binom{5}{3} = 10$ sets of three edges. Three edges on four vertices connect everything exactly when they contain no cycle, and the only $3$ -edge cycles are the triangles $\{e_1, e_2, e_5\}$ (vertices $1, 2, 3$ ) and $\{e_3, e_4, e_5\}$ (vertices $1, 3, 4$ ). So there are $10 - 2 = 8$ spanning trees, matching $\det \mathbf{L}_0$ .
(c) Deleting row $4$ of $\mathbf{N}$ deletes row $4$ of $\mathbf{N}\mathbf{N}^{\top}$ (row view) and column $4$ of $\mathbf{N}\mathbf{N}^{\top}$ (column view of $\mathbf{N}^{\top}$ ), by Theorem 0.9.2. So $\mathbf{L}_0 = \mathbf{N}_0\mathbf{N}_0^{\top}$ , with $\mathbf{N}_0 \in M_{3 \times 5}(\mathbb{R})$ , and Corollary 7.7.3 gives $\det \mathbf{L}_0 = \sum_{|S| = 3} (\det (\mathbf{N}_0)_{[3],S})^2$ , one term for each set $S$ of three edges.
(d) For $S = \{e_1, e_2, e_3\}$ , $(\mathbf{N}_0)_{[3],S} = \begin{pmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{pmatrix}$ , which is lower triangular with determinant $1$ (Theorem 7.4.6). For $S = \{e_1, e_2, e_5\}$ , the columns are $(1, -1, 0)$ , $(0, 1, -1)$ , $(1, 0, -1)$ , and the third is the sum of the first two: going around the cycle $1 \to 2 \to 3$ equals going directly $1 \to 3$ . So the columns are dependent and the minor is $0$ by Theorem 7.2.1. Thus the non-tree contributes $0^2$ and the tree contributes $1^2$ .

Exercise (C2: Rank does not depend on the field)

Let $K$ be a subfield of a field $L$ (Definition 1.9.1), and let $\mathbf{A} \in M_{m \times n}(K)$ . We may also regard $\mathbf{A}$ as a matrix in $M_{m \times n}(L)$ .

(a) Explain why each minor $\det \mathbf{A}_{I,J}$ is the same element whether computed in $K$ or in $L$ .
(b) Prove that the rank of $\mathbf{A}$ over $K$ equals its rank over $L$ .
(c) Deduce: if a system $\mathbf{A}\mathbf{x} = \mathbf{0}$ with rational coefficients has a non-zero complex solution, it has a non-zero rational solution.

Solution.

(a) By Definition 7.4.1, $\det \mathbf{A}_{I,J}$ is a finite sum of $\pm$ products of entries of $\mathbf{A}$ . The entries lie in $K$ , and $K$ has the same addition and multiplication as $L$ , so the sum is the same element of $K \subseteq L$ .
(b) If $\mathbf{A} = 0$ , both ranks are $0$ . Otherwise, by Theorem 7.7.1 (a) applied over $K$ and over $L$ , each rank is the largest $k$ for which some $k \times k$ minor is non-zero. By (a) the list of minors, and which of them are non-zero, is the same in both cases. Hence the two ranks agree.
(c) Take $K = \mathbb{Q}$ , $L = \mathbb{C}$ . A non-zero complex solution means $\operatorname{nullity} \mathbf{A} \ge 1$ over $\mathbb{C}$ , so $\operatorname{rank}_{\mathbb{C}} \mathbf{A} \le n - 1$ by Theorem 3.5.7. By (b), $\operatorname{rank}_{\mathbb{Q}} \mathbf{A} \le n - 1$ , so $\operatorname{nullity} \mathbf{A} \ge 1$ over $\mathbb{Q}$ , and a non-zero rational solution exists.