Why a Product Has a Rank Lower Bound
For compatible matrices, the familiar upper bounds on the rank of a product say that multiplication cannot produce more independent output directions than either factor allows. Sylvester’s rank inequality gives a complementary statement: the product cannot lose too many directions. The amount it may lose is controlled by the dimension where the two matrices meet, namely the number of columns of the first matrix and rows of the second.
Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\) and \(\mathbf{B}\in\mathbb{R}^{n\times p}\). Their product \(\mathbf{A}\mathbf{B}\) is an \(m\times p\) matrix. The shared dimension is \(n\), not necessarily either outer dimension \(m\) or \(p\). For a matrix \(\mathbf{M}\), its rank \(\operatorname{rank}\mathbf{M}\) is the dimension of its column space \(\operatorname{Col}\mathbf{M}\). Its null space \(\operatorname{Nul}\mathbf{M}\) consists of the vectors mapped to zero by multiplication by \(\mathbf{M}\).
The subtraction of \(n\) reflects the possibility that some directions produced by \(\mathbf{B}\) are sent to zero by \(\mathbf{A}\). In fact, \(\mathbf{B}\) sends vectors in \(\mathbb{R}^p\) into \(\mathbb{R}^n\), and \(\mathbf{A}\) then acts on that intermediate space. The key question is how much the image of \(\mathbf{B}\) overlaps the null space of \(\mathbf{A}\).
Proof by Restricting the First Map
We use the Rank-Nullity Theorem for linear maps between finite-dimensional vector spaces: the dimension of the domain is the dimension of the kernel plus the dimension of the image. In particular, for the map \(\mathbf{x}\mapsto\mathbf{A}\mathbf{x}\) from \(\mathbb{R}^n\) to \(\mathbb{R}^m\), it gives \(\dim(\operatorname{Nul}\mathbf{A})=n-\operatorname{rank}\mathbf{A}\). Apply rank-nullity again, this time to the restriction of \(\mathbf{A}\) to the column space of \(\mathbf{B}\).
Proof. Let \(U=\operatorname{Col}\mathbf{B}\), a subspace of \(\mathbb{R}^n\), and consider the linear map \(T:U\to\mathbb{R}^m\) defined by \(T(\mathbf{u})=\mathbf{A}\mathbf{u}\). Its image is \(\operatorname{Col}(\mathbf{A}\mathbf{B})\): every vector in that product’s column space has the form \(\mathbf{A}\mathbf{B}\mathbf{x}\), which equals \(T(\mathbf{B}\mathbf{x})\), and every \(\mathbf{u}\in U\) has the form \(\mathbf{B}\mathbf{x}\). Its kernel is \(U\cap\operatorname{Nul}\mathbf{A}\), since \(T(\mathbf{u})=\mathbf{0}\) exactly when \(\mathbf{u}\in U\) and \(\mathbf{A}\mathbf{u}=\mathbf{0}\). Rank-nullity for \(T\) therefore gives $$ \operatorname{rank}(\mathbf{A}\mathbf{B}) =\dim U-\dim\bigl(U\cap\operatorname{Nul}\mathbf{A}\bigr). $$ Because \(U=\operatorname{Col}\mathbf{B}\), we have \(\dim U=\operatorname{rank}\mathbf{B}\). Also, \(U\cap\operatorname{Nul}\mathbf{A}\) is a subspace of \(\operatorname{Nul}\mathbf{A}\), so its dimension is at most \(\dim(\operatorname{Nul}\mathbf{A})=n-\operatorname{rank}\mathbf{A}\). Substitution yields $$ \operatorname{rank}(\mathbf{A}\mathbf{B}) \geq \operatorname{rank}\mathbf{B}-(n-\operatorname{rank}\mathbf{A}) =\operatorname{rank}\mathbf{A}+\operatorname{rank}\mathbf{B}-n. $$ This proves the inequality. \(\square\)
The argument also explains the bound: the product has rank equal to \(\operatorname{rank}\mathbf{B}\) minus the dimension of the directions in \(\operatorname{Col}\mathbf{B}\) that \(\mathbf{A}\) annihilates. That loss cannot exceed the full nullity of \(\mathbf{A}\), which is \(n-\operatorname{rank}\mathbf{A}\).
Applying the Inequality
Worked Example: Equality with a Nonzero Product
Let $$ \mathbf{A}=\begin{bmatrix}1&0&0\\0&1&0\end{bmatrix}, \qquad \mathbf{B}=\begin{bmatrix}1&0\\0&0\\0&1\end{bmatrix}. $$ Both matrices have rank \(2\). For \(\mathbf{A}\), its first two columns are \(\begin{bmatrix}1\\0\end{bmatrix}\) and \(\begin{bmatrix}0\\1\end{bmatrix}\), so they are independent and span \(\mathbb{R}^2\). For \(\mathbf{B}\), its two columns are independent: if \(c_1\begin{bmatrix}1\\0\\0\end{bmatrix}+c_2\begin{bmatrix}0\\0\\1\end{bmatrix}=\mathbf{0}\), then the first and third coordinates give \(c_1=c_2=0\).
Multiply the matrices by taking each row of \(\mathbf{A}\) against each column of \(\mathbf{B}\):
The product has rank \(1\), since its first column is nonzero and its second column is zero. The bound is \(2+2-3=1\), so equality holds. Here \(\operatorname{Nul}\mathbf{A}\) is spanned by \(\begin{bmatrix}0\\0\\1\end{bmatrix}\), and that vector is in \(\operatorname{Col}\mathbf{B}\). The direction in the image of \(\mathbf{B}\) that \(\mathbf{A}\) sends to zero accounts for the rank loss.
Worked Example: A Strict Inequality
Keep \(\mathbf{A}\) as above, but take $$ \mathbf{B}=\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}. $$ The columns of \(\mathbf{B}\) are independent: if \(c_1\begin{bmatrix}1\\0\\1\end{bmatrix}+c_2\begin{bmatrix}0\\1\\0\end{bmatrix}=\mathbf{0}\), the first and second coordinates force \(c_1=c_2=0\). Thus \(\operatorname{rank}\mathbf{B}=2\), and, as before, \(\operatorname{rank}\mathbf{A}=2\).
Multiplication gives $$ \mathbf{A}\mathbf{B} = \begin{bmatrix} 1\cdot1+0\cdot0+0\cdot1 & 1\cdot0+0\cdot1+0\cdot0\\ 0\cdot1+1\cdot0+0\cdot1 & 0\cdot0+1\cdot1+0\cdot0 \end{bmatrix} = \begin{bmatrix}1&0\\0&1\end{bmatrix}. $$ The product has rank \(2\). Sylvester’s bound is \(2+2-3=1\), so \(2>1\): the inequality is strict. In this case \(\operatorname{Col}\mathbf{B}\) is spanned by \(\begin{bmatrix}1\\0\\1\end{bmatrix}\) and \(\begin{bmatrix}0\\1\\0\end{bmatrix}\); it does not contain \(\begin{bmatrix}0\\0\\1\end{bmatrix}\), the direction in \(\operatorname{Nul}\mathbf{A}\). Consequently, \(\mathbf{A}\) annihilates none of the nonzero directions in \(\operatorname{Col}\mathbf{B}\), and no rank is lost.
Worked Example: A Zero Product at the Lower Bound
Let $$ \mathbf{A}=\begin{bmatrix}1&0&0\\0&1&0\end{bmatrix}, \qquad \mathbf{B}=\begin{bmatrix}0&0\\0&0\\1&0\end{bmatrix}. $$ The rank of \(\mathbf{A}\) is \(2\). The first column of \(\mathbf{B}\) is nonzero and its second column is zero, so \(\operatorname{rank}\mathbf{B}=1\). Their product is $$ \mathbf{A}\mathbf{B} = \begin{bmatrix} 1\cdot0+0\cdot0+0\cdot1 & 1\cdot0+0\cdot0+0\cdot0\\ 0\cdot0+1\cdot0+0\cdot1 & 0\cdot0+1\cdot0+0\cdot0 \end{bmatrix} = \begin{bmatrix}0&0\\0&0\end{bmatrix}. $$ Thus \(\operatorname{rank}(\mathbf{A}\mathbf{B})=0\), and the bound is \(2+1-3=0\). The inequality permits a zero product here because the image of \(\mathbf{B}\) lies entirely in \(\operatorname{Nul}\mathbf{A}\).
Exactly When Does Equality Hold?
Proof. Put \(U=\operatorname{Col}\mathbf{B}\). The rank-nullity calculation in the proof above gives $$ \operatorname{rank}(\mathbf{A}\mathbf{B}) =\operatorname{rank}\mathbf{B}-\dim\bigl(U\cap\operatorname{Nul}\mathbf{A}\bigr). $$ The lower bound is \(\operatorname{rank}\mathbf{B}-\dim(\operatorname{Nul}\mathbf{A})\). Therefore equality holds exactly when $$ \dim\bigl(U\cap\operatorname{Nul}\mathbf{A}\bigr)=\dim(\operatorname{Nul}\mathbf{A}). $$ Since \(U\cap\operatorname{Nul}\mathbf{A}\) is a subspace of \(\operatorname{Nul}\mathbf{A}\), equality of their finite dimensions holds exactly when the two subspaces are equal. That equality is equivalent to \(\operatorname{Nul}\mathbf{A}\subseteq U=\operatorname{Col}\mathbf{B}\). This proves both directions. \(\square\)
This criterion says that the lower bound is attained precisely when the image of \(\mathbf{B}\) contains every direction that \(\mathbf{A}\) sends to zero. The first and third worked examples satisfy this condition; the strict-inequality example does not.
Common Pitfall: Subtracting the Wrong Dimension
The subtracted number in Sylvester’s inequality is the inner dimension \(n\). It is not the number of rows or columns of the product. For example, the matrices in the strict-inequality example have size \(2\times3\) and \(3\times2\). Their product has size \(2\times2\), but the shared dimension is \(3\). Using the product’s row count as the subtraction would incorrectly predict $$ \operatorname{rank}(\mathbf{A}\mathbf{B})\geq 2+2-2=2. $$ That contradicts the directly computed product \(\mathbf{A}\mathbf{B}=\mathbf{I}_2\) only in no way here—the rank is \(2\)—but it is not a valid application of the theorem and would give a false bound in other cases. In the first example, the same mistaken calculation would predict rank at least \(2\), while the actual product has rank \(1\). The correct subtraction is the number of columns of \(\mathbf{A}\), which must equal the number of rows of \(\mathbf{B}\).
When applying the inequality, first write down the matrix sizes, then identify the common inner dimension. Compute or establish the two factor ranks, subtract that inner dimension, and compare the result with the rank of the product if it is known. A negative lower bound is valid but uninformative, because rank is already nonnegative; it does not imply that a product has negative rank or that the inequality has failed.
Sylvester’s inequality is useful when the product is difficult to row reduce but the ranks of its factors are known. It can also rule out claims about a product’s rank: if a proposed product rank is below \(\operatorname{rank}\mathbf{A}+\operatorname{rank}\mathbf{B}-n\), at least one of the proposed factor ranks or the claimed product rank must be wrong.
Check Your Understanding
For each question, identify the inner dimension before applying the inequality.
- If \(\mathbf{A}\in\mathbb{R}^{4\times6}\) has rank \(4\) and \(\mathbf{B}\in\mathbb{R}^{6\times3}\) has rank \(2\), what lower bound does Sylvester’s inequality give for \(\operatorname{rank}(\mathbf{A}\mathbf{B})\)?
- For compatible matrices with inner dimension \(5\), ranks \(3\) and \(4\), and product rank \(2\), is the stated information consistent with Sylvester’s inequality?
- State the condition on \(\operatorname{Nul}\mathbf{A}\) and \(\operatorname{Col}\mathbf{B}\) that is equivalent to equality in the inequality.
- Suppose \(\operatorname{Col}\mathbf{B}\subseteq\operatorname{Nul}\mathbf{A}\). What is \(\mathbf{A}\mathbf{B}\), and what does the inequality then require of the factor ranks and inner dimension?
- For \(\mathbf{A}\in\mathbb{R}^{3\times4}\) and \(\mathbf{B}\in\mathbb{R}^{4\times2}\), which dimension is subtracted in Sylvester’s bound, and why?
