I notice this property on the wikipedia: https://en.wikipedia.org/wiki/Rank_(linear_algebra)
We assume that A is an m × n matrix, and we define the linear map f by f(x) = Ax as above
The rank of A is equal to r if and only if there exists an invertible m × m matrix X and an invertible n × n matrix Y such that
${\displaystyle XAY={\begin{bmatrix}I_{r}&0\\0&0\\\end{bmatrix}},}$
where Ir denotes the r × r identity matrix.
But I can't find a proof of such a property, I would imagine it has something to do with Gaussian elimination?
Best Answer
It’s not quite Gaussian elimination, since that only left-multiplies by invertible matrices. The underlying idea is that you can find bases for the domain and codomain in which the matrix of $f$ has the requisite form. $X$ and $Y$ are just the corresponding change-of-basis matrices.
Recall that the columns of the matrix are the images $f(v_i)$ of the domain’s basis vectors. So, choose an ordered basis $(v_{r+1},\dots,v_m)$ for the kernel of $f$ and extend it to a complete basis $(v_1,\dots,v_r,v_{r+1},\dots,v_m)$ for the domain. Relative to this basis, the first $r$ columns of the matrix are nonzero, while the rest are zero.
The images $\{f(v_1),\dots,f(v_r)\}$ of the first $r$ basis vectors are linearly independent (prove this!). Extend this to an ordered basis $(f(v_1),\dots,f(v_r),w_{r+1},\dots,w_n)$ of the codomain. Relative to this basis, $f(v_1)=(1,0,0,\dots,0)^T$, $f(v_2)=(0,1,0,\dots,0)^T$, and so on, which gives you $I_r$ padded below with zeros for the first $r$ columns of the matrix.
You can compute a suitable $X$ and $Y$ by performing Gaussian elimination twice. First, augment $A$ by the appropriately-sized identity matrix and reduce to obtain $$[A\mid I_m] \to [B\mid X].$$ The last $m-r+1$ rows of $B$ will be zero as required, and $XA=B$. Then, augment $B^T$ and reduce again: $$[B^T\mid I_n] \to [C^T\mid Y^T].$$ The last $n-r+1$ columns of $C$ are zero, the last $m-r+1$ were already zero when you obtained $B$, and since $C^T$ is in RREF, the upper-left block is $I_r$. Finally, C^T=Y^TB^T, so $C=XAY$. The fact that the row rank and column rank are equal is part of the content of the Rank-Nullity theorem, but you can see why that must be so from the basis construction above. Observe, too, that $X$ and $Y$ are not unique: you are free to choose the kernel basis and its extension to a basis of the domain, as well as the extension of the image of the kernel basis to an image of the codomain. Each of these choices potentially generates a different $X$ and $Y$.