---- > [!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**. Sometimes the more drastic process allowing for column operations as well is called 'Gaussian Elimination', it is the field case of converting a matrix into [[Gaussian elimination|Smith normal form]]. > ^4fabe8 > [!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 $\hat{d}_{n}=\begin{bmatrix} 1 & \\ & d_{n}^{\Sigma} \end{bmatrix}$ > [!basicexample] > Compute the Smith decomposition $D=PAQ$ over $\mathbb{Q}$ for the [[matrix]] $A=\begin{bmatrix} > 1 & 2 & 1 \\ > -2 & -4 & -2 > \end{bmatrix}$ > and use this to write down [[basis|basis vectors]] for its [[kernel of a linear map|kernel]] and image. > > > From the perspective of elementary operations, $D=\begin{bmatrix}1 & 0 & 0 \\0 & 0 & 0\end{bmatrix}$ may obtained from $A$ by > 1. adding $2 \cdot$ the first row of $A$ to the second, > 2. adding $-\frac{1}{2}\cdot$ the second column of the result to the third > 3. adding $-2\cdot$ the first column of the result to the second. > > In terms of elementary matrices, $(1)$ is accomplished via left multiplication by $E_{1}=\begin{bmatrix} > 1 & \\ > 2& 1 > \end{bmatrix}$ > while $(2)$ and $(3)$ are accomplished via right multiplication by $E_{2}=\begin{bmatrix} > 1 & & \\ > & 1 & -\frac{1}{2} \\ > & & 1 > \end{bmatrix}, \, \, \, \, E_{3}= \begin{bmatrix} > 1 & -2 & \\ > & 1 & \\ > & & 1 > \end{bmatrix}$ > respectively. The result is $D=\underbrace{ E_{1} }_{ :=P } A \underbrace{ E_{2} E_{3} }_{ := Q }$ > where $D=\begin{bmatrix} > 1 & & \\ > & & & > \end{bmatrix}, P= \begin{bmatrix} > 1 & \\ > 2& 1 > \end{bmatrix}, Q= \begin{bmatrix} > 1 & -2 & \\ > & 1 & -\frac{1}{2} \\ > & & 1 > \end{bmatrix}.$ > In turn, $A=P ^{-1} D Q ^{-1}$. By construction, $\operatorname{ker }D$ has [[basis]] $\{ e_{2},e_{3} \}$. Thus to find a [[basis]] for $\operatorname{ker } A$, we seek vectors $v,w$ for which $Q^{-1}v=e_{2}$, $Q ^{-1}w=e_{3}$. Namely, we see that the final two columns $\{ Qe_{2}, Qe_{3} \}$ of $Q$ form a [[basis]] for $\operatorname{ker }A$. $\operatorname{im }D=\operatorname{im }D Q ^{-1}$ has basis $\{ e_{1} \}$. A [[basis]] for $\operatorname{im }A$, then, is just $P ^{-1} e_{1}=\begin{bmatrix}1 \\ -2\end{bmatrix}$. - [ ] [[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. $a_{1 1}$ (or the entry that becomes $a_{11}$ after row/column swaps) is a **pivot**. > 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 > ```