# Proof of Rank Property: ${\displaystyle XAY={\begin{bmatrix}I_{r}&0\\0&0\\\end{bmatrix}},}$

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?

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$$.

Hint

This is one of the almost direct consequences of SVD. Every $$m\times n$$ matrix $$A$$ can be decomposed as follows$$A=UDV$$where $$U_{m\times m}$$ and $$V_{n\times n}$$ are unitary and $$D_{m\times n}$$ is diagonal and has exactly $$r$$ non-zero entries. The rest of the proof on finding $$X$$ and $$Y$$ is easy.

So $$A$$ represents a linear map $$u$$ between a vector space $$E$$ of dimension $$m$$ to a vector space $$F$$ of dimension $$n$$.

Using the rank-nullity theorem, we know that $$\dim(\ker(u)) + \dim(u(E))=\dim E = m$$. Hence, we can find a basis $$\mathcal E = (e_1, \dots, e_r, e_{r+1}, \dots , e_m)$$ of $$E$$ such that $$(e_{r+1}, \dots , e_m)$$ is a basis of $$\ker(u)$$.

Denote for $$1 \le i \le r$$ $$f_i = u(e_i)$$. $$(f_1, \dots, f_r)$$ is a linearly independent family of vectors of $$F$$. Complete this family into a basis $$\mathcal F =(f_1, \dots, f_r, f_{r+1}, \dots , f_n)$$. The matrix $$\mathcal M_{\mathcal E,\mathcal F}(u)$$of $$u$$ in the basis $$\mathcal E, \mathcal F$$ is exactly

$$J_r=\begin{bmatrix}I_{r}&0\\0&0\\\end{bmatrix}$$ as $$u(e_i)=0$$ for $$r+1 \le i \le m$$ and $$u(e_i)=f_i$$ for $$1 \le i \le r$$.

Therefore it exist invertible change of basis matrices $$X, Y$$ such that $$XAY = J_r.$$

The desired result.