Probability that an overdetermined linear system is consistent

Question

On the wikipedia page "Overdetermined System," I came across the claim that an overdetermined system is almost always inconsistent when constructed with random coefficients. Is anyone familiar with a proof for this or somewhere that I could read more about it? I am interested in the case of linear systems with real coefficients.

Answer 1

By Rouche-Capelli’s theorem the system Ax=b is inconsistent iff rkA <rk(A|b). Since if the joint distribution of the entries of a matrix is absolutely continuous, it is known that it has full rank almost surely (a.s.), it follows that for a matrix A of dimensions mxn, m>n, rkA=n=min(m,n)<m a.s. and rk(A|b)=n+1=min(n+1,m)<=m a.s. Hence the two ranks are different almost surely. That an absolutely continuous matrix has full rank a.s. follows from the set of zeroes of a non-constant polynomial having Lebesgue measure zero. If M is the set of minors of A of size n, for example, the polynomial in the entries of A constructed by adding up all the squares of these minors’ determinants is a non constant polynomial, as A varies. A is rankdeficient iff this polynomial is zero, hence it is rank deficient with its entries belonging to a Lebesgue set of measure zero. Hence with probability zero by absolute continuity. So the matrix is almost surely full rank. Same goes for (A|b) with minor adjustments.