1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.