---- > [!theorem] Theorem. ([[Gaussian elimination]]) > Over a [[field]], every $m \times n$ [[matrix]] is [[equivalent matrices|equivalent]] to a [[matrix]] of the form $\left[ \begin{array}{c|c} I_r & 0 \\ \hline 0 & 0 \end{array} \right]$ where $r \leq \text{min}(m,n)$, $I_{r}$ is the [[identity matrix]], and '$0 stands for zero matrices of appropriate size. > The algorithm accomplishing this, outlined below, obtains the above [[matrix]] via a successive application of suitable [[elementary operation|elementary operations]] to *both* rows and columns.' > If accomplished using only row operations (left-multiplication by elementary matrices), the process is called **Gaussian elimination**. (Though sometimes the more drastic process allowing for column operations as well is called 'Gaussian Elimination'). ^theorem > [!proof] Corollary. > Each [[equivalence class]] of [[matrix|matrices]] *over a [[field]]* has a representative of the type > $\left[ \begin{array}{c|c} I_r & 0 \\ \hline 0 & 0 \end{array} \right],$ > that is, the $m \times n$ [[matrix|matrices]] over a field are classified up to matrix [[equivalent matrices|equivalence]] by [[rank]]. > ^proof - [ ] [[TODO]] connect to [[every linear bijection is a composition of primitive linear maps]] - [ ] [[TODO]] explore when it is sufficient to only consider row-equivalence > [!proof]+ Proof. ([[Gaussian elimination]]) > Let $A=(a_{ij})$ be any rectangular [[matrix]]. Try to swap rows and columns as necessary (an [[elementary operation]]) to allow the assumption that $a_{11} \neq 0$; if this cannot be done then our submatrix is actually the zero matrix, at which point the process is finished. > Now, multiplying the first row by $a_{11}^{-1}$, we may assume $a_{11}=1$: $\begin{bmatrix} 1 & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{1n} \\ \vdots & \vdots & \ddots & \vdots & \\ a_{n1} & a_{n 2} & \cdots & a_{nn}. \end{bmatrix}$ Now add to the second row the $(-a_{21})$-multiple of the first row to clear the $(2,1)$ entry. Do the same to clear the $(3,1),\dots,(n,1)$ entries: $\begin{bmatrix} 1 & a_{12} & \cdots & a_{1n} \\ 0 & a_{22}' & \cdots & a_{1n} '\\ \vdots & \vdots & \ddots & \vdots & \\ 0 & a_{n2}' & \cdots & a_{nn}'. \end{bmatrix}$ Now add to the second column the $(-a_{12})$-multiple of the first; this clears the $(1,2)$ entry. And repeat as before to get a reduced [[matrix]] of the form $\begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & a_{22}' & \cdots & a_{1n}' \\ \vdots & \vdots & \ddots & \vdots & \\ 0 & a_{n2}' & \cdots & a_{n n}' \end{bmatrix}=\left[ \begin{array}{c|c} 1 & 0 \\ \hline 0 & A' \end{array} \right].$ Repeating the process on $A'$ and on subsequent smaller matrices will yield the desired form. ---- #### ----- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```