Sylvester rank inequality

Sylvester rank inequality is a classical result in Linear algebra giving a lower bound on the rank of a product of two matrices in terms of the ranks of the factors. The inequality connects foundational results such as the Rank–nullity theorem, Gaussian elimination, and the theory developed by James Joseph Sylvester with later work by Ferdinand Frobenius, Issai Schur, and contributors to matrix theory across Cambridge University and École Normale Supérieure traditions. It serves in contexts ranging from control theory and signal processing to structural results in representation theory and algebraic geometry.

Statement

Let A be an m×n matrix and B an n×p matrix over a field (or division ring). Sylvester's inequality states that rank(A) + rank(B) − n ≤ rank(AB). Equivalently, rank(AB) ≥ rank(A) + rank(B) − n, where n is the inner dimension of the product. This inequality refines trivial bounds that involve rank monotonicity under multiplication and complements classical relations such as the Rank–nullity theorem and the Frobenius rank inequality.

Proofs

Standard proofs exploit column- and row-space arguments tying linear independence to image and kernel dimensions. One proof uses the chain of subspaces: the column space of AB is contained in the column space of A and the nullspace of B intersects the domain; applying dimension counts via Rank–nullity theorem yields the inequality. Alternative proofs use matrix factorizations: perform Gaussian elimination or compute reduced row echelon form to produce rank-revealing factorizations A = U [Ir 0] V and B = X [Is; 0] Y, where U, V, X, Y are invertible and Ir, Is are identity blocks; counting overlapping identity blocks gives the same bound. More algebraic proofs invoke properties of determinants on suitable minors and relate nonvanishing minors of A and B to minors of AB; these connect to ideas in Plücker relations and multilinear algebra. Operator-theoretic proofs use bounded linear operator analogues on finite-dimensional Hilbert spaces and reduce to finite matrix statements, paralleling arguments from functional analysis.

Equality cases and characterizations

Equality in Sylvester's inequality occurs precisely when the column space of AB equals the intersection of the column space of A with the image of B (viewed as a map), and the dimensions align so that no further rank loss beyond the dimension of the intermediate space occurs. Characterizations involve decompositions: there exist invertible matrices bringing A and B into block forms where overlapping identity sizes achieve equality. In terms of kernels, equality holds when ker(B) intersects the complement of ker(A) in a way that saturates the bound predicted by Rank–nullity theorem. For matrices over algebraically closed fields, equality conditions can be restated via genericity and Zariski-open conditions, linking to stratifications studied in algebraic geometry and to orbit descriptions under the action of general linear groups.

Generalizations and related inequalities

Sylvester's inequality sits among several rank inequalities. The Frobenius rank inequality refines relationships between ranks of three matrices: rank(AB) + rank(BC) ≤ rank(B) + rank(ABC). The Weyl inequalities compare eigenvalues rather than ranks for Hermitian matrices and relate to interlacing phenomena used in spectral graph theory. The Cauchy–Binet formula gives exact expressions for minors of products and underpins determinant-based generalizations. Matrix inequality families developed in the schools of Issai Schur and Hermann Weyl include results on singular values such as Horn's inequalities and the Mirsky inequalities, which complement Sylvester-type bounds. Noncommutative generalizations appear in the theory of modules over principal ideal domains and in categorical treatments via exact sequences and Hom functors in homological algebra.

Applications and examples

Sylvester's inequality is used to deduce rank properties in linear systems arising in control theory, model reduction in signal processing, and identifiability in statistical factor analysis. It provides quick bounds in computing ranks of composition maps in representation theory (e.g., compositions of intertwiners) and in proving impossibility results in combinatorial matrix completion problems studied by researchers at institutions like MIT and Stanford University. Concrete examples: take A of rank r and B of rank s with inner dimension n; if r + s > n then AB cannot have rank less than r + s − n, which yields constructive constraints in network coding and in the design of measurement matrices in compressed sensing. In computational linear algebra, Sylvester's inequality helps optimize pivoting strategies during LU decomposition and gives worst-case guarantees for rank-revealing factorizations used in libraries developed by groups associated with Numerical Linear Algebra research centers.

Category:Linear algebra