Elementary Matrices

$\newenvironment {prompt}{}{} \newcommand {\ungraded }[0]{} \newcommand {\definedTerm }[1]{\textbf {#1}} \newcommand {\dfn }[1]{\textbf {#1}} \newcommand {\wt }[0]{\widetilde } \newcommand {\ov }[0]{\overline } \newcommand {\inj }[0]{\rightarrowtail } \newcommand {\surj }[0]{\twoheadrightarrow } \newcommand {\harpoon }[0]{\overset {\rightharpoonup }} \newcommand {\orderof }[1]{\sim #1} \newcommand {\Z }[0]{\mathbb {Z}} \newcommand {\reals }[0]{\mathbb {R}} \newcommand {\real }[1]{\mathbb {R}^{#1}} \newcommand {\complexes }[0]{\mathbb {C}} \newcommand {\complex }[1]{\mathbb {C}^{#1}} \newcommand {\CC }[0]{\mathbb {C}} \newcommand {\conjugate }[1]{\overline {#1}} \newcommand {\modulus }[1]{\left \lvert #1\right \rvert } \newcommand {\zerovector }[0]{\vect {0}} \newcommand {\zeromatrix }[0]{\mathcal {O}} \newcommand {\innerproduct }[2]{\left \langle #1,\,#2\right \rangle } \newcommand {\norm }[1]{\left \lVert #1\right \rVert } \newcommand {\dimension }[1]{\dim \left (#1\right )} \newcommand {\nullity }[1]{n\left (#1\right )} \newcommand {\rank }[1]{r\left (#1\right )} \newcommand {\ds }[0]{\oplus } \newcommand {\detname }[1]{\det \left (#1\right )} \newcommand {\detbars }[1]{\left \lvert #1\right \rvert } \newcommand {\trace }[1]{t\left (#1\right )} \newcommand {\sr }[1]{#1^{1/2}} \newcommand {\spn }[1]{\left \langle #1\right \rangle } \newcommand {\nsp }[1]{\mathcal {N}\!\left (#1\right )} \newcommand {\csp }[1]{\mathcal {C}\!\left (#1\right )} \newcommand {\rsp }[1]{\mathcal {R}\!\left (#1\right )} \newcommand {\lns }[1]{\mathcal {L}\!\left (#1\right )} \newcommand {\per }[1]{#1^\perp } \newcommand {\augmented }[2]{\left \lbrack \left .#1\,\right \rvert \,#2\right \rbrack } \newcommand {\linearsystem }[2]{\mathcal {LS}\!\left (#1,\,#2\right )} \newcommand {\homosystem }[1]{\linearsystem {#1}{\zerovector }} \newcommand {\rowopswap }[2]{R_{#1}\leftrightarrow R_{#2}} \newcommand {\rowopmult }[2]{#1R_{#2}} \newcommand {\rowopadd }[3]{#1R_{#2}+R_{#3}} \newcommand {\leading }[1]{\fbox {#1}} \newcommand {\rref }[0]{\xrightarrow {\text {RREF}}} \newcommand {\elemswap }[2]{E_{#1,#2}} \newcommand {\elemmult }[2]{E_{#2}\left (#1\right )} \newcommand {\elemadd }[3]{E_{#2,#3}\left (#1\right )} \newcommand {\scalarlist }[2]{{#1}_{1},\,{#1}_{2},\,{#1}_{3},\,\ldots ,\,{#1}_{#2}} \newcommand {\vect }[1]{\mathbf {#1}} \newcommand {\colvector }[1]{\begin {bmatrix}#1\end {bmatrix}} \newcommand {\vectorcomponents }[2]{\colvector {#1_{1}\\#1_{2}\\#1_{3}\\\vdots \\#1_{#2}}} \newcommand {\vectorlist }[2]{\vect {#1}_{1},\,\vect {#1}_{2},\,\vect {#1}_{3},\,\ldots ,\,\vect {#1}_{#2}} \newcommand {\vectorentry }[2]{\left \lbrack #1\right \rbrack _{#2}} \newcommand {\matrixentry }[2]{\left \lbrack #1\right \rbrack _{#2}} \newcommand {\lincombo }[3]{#1_{1}\vect {#2}_{1}+#1_{2}\vect {#2}_{2}+#1_{3}\vect {#2}_{3}+\cdots +#1_{#3}\vect {#2}_{#3}} \newcommand {\matrixcolumns }[2]{\left \lbrack \vect {#1}_{1}|\vect {#1}_{2}|\vect {#1}_{3}|\ldots |\vect {#1}_{#2}\right \rbrack } \newcommand {\transpose }[1]{#1^{t}} \newcommand {\inverse }[1]{#1^{-1}} \newcommand {\submatrix }[3]{#1\left (#2|#3\right )} \newcommand {\adj }[1]{\transpose {\left (\conjugate {#1}\right )}} \newcommand {\adjoint }[1]{#1^\ast } \newcommand {\set }[1]{\left \{#1\right \}} \newcommand {\setparts }[2]{\left \lbrace #1\,\middle |\,#2\right \rbrace } \newcommand {\card }[1]{\left \lvert #1\right \rvert } \newcommand {\setcomplement }[1]{\overline {#1}} \newcommand {\charpoly }[2]{p_{#1}\left (#2\right )} \newcommand {\eigenspace }[2]{\mathcal {E}_{#1}\left (#2\right )} \newcommand {\eigensystem }[3]{\lambda &amp;=#2&amp;\eigenspace {#1}{#2}&amp;=\spn {\set {#3}}} \newcommand {\geneigenspace }[2]{\mathcal {G}_{#1}\left (#2\right )} \newcommand {\algmult }[2]{\alpha _{#1}\left (#2\right )} \newcommand {\geomult }[2]{\gamma _{#1}\left (#2\right )} \newcommand {\indx }[2]{\iota _{#1}\left (#2\right )} \newcommand {\ltdefn }[3]{#1\colon #2\rightarrow #3} \newcommand {\lteval }[2]{#1\left (#2\right )} \newcommand {\ltinverse }[1]{#1^{-1}} \newcommand {\restrict }[2]{{#1}|_{#2}} \newcommand {\preimage }[2]{#1^{-1}\left (#2\right )} \newcommand {\rng }[1]{\mathcal {R}\!\left (#1\right )} \newcommand {\krn }[1]{\mathcal {K}\!\left (#1\right )} \newcommand {\compose }[2]{{#1}\circ {#2}} \newcommand {\vslt }[2]{\mathcal {LT}\left (#1,\,#2\right )} \newcommand {\isomorphic }[0]{\cong } \newcommand {\similar }[2]{\inverse {#2}#1#2} \newcommand {\vectrepname }[1]{\rho _{#1}} \newcommand {\vectrep }[2]{\lteval {\vectrepname {#1}}{#2}} \newcommand {\vectrepinvname }[1]{\ltinverse {\vectrepname {#1}}} \newcommand {\vectrepinv }[2]{\lteval {\ltinverse {\vectrepname {#1}}}{#2}} \newcommand {\matrixrep }[3]{M^{#1}_{#2,#3}} \newcommand {\matrixrepcolumns }[4]{\left \lbrack \left .\vectrep {#2}{\lteval {#1}{\vect {#3}_{1}}}\right |\left .\vectrep {#2}{\lteval {#1}{\vect {#3}_{2}}}\right |\left .\vectrep {#2}{\lteval {#1}{\vect {#3}_{3}}}\right |\ldots \left |\vectrep {#2}{\lteval {#1}{\vect {#3}_{#4}}}\right .\right \rbrack } \newcommand {\cbm }[2]{C_{#1,#2}} \newcommand {\jordan }[2]{J_{#1}\left (#2\right )} \newcommand {\hadamard }[2]{#1\circ #2} \newcommand {\hadamardidentity }[1]{J_{#1}} \newcommand {\hadamardinverse }[1]{\widehat {#1}} \newcommand {\id }[0]{\mathrm {id}} \newcommand {\C }[0]{\mathbb {C}} \newcommand {\R }[0]{\mathbb {R}} \newcommand {\Q }[0]{\mathbb {Q}} \newcommand {\N }[0]{\mathbb {N}} \newcommand {\F }[0]{\mathbb {F}} \newcommand {\bbH }[0]{\mathbb {H}} \newcommand {\SO }[0]{\operatorname {SO}} \newcommand {\Dten }[0]{D_{10}} \newcommand {\calC }[0]{\mathcal {C}} \newcommand {\calD }[0]{\mathcal {D}} \newcommand {\calF }[0]{\mathcal {F}} \newcommand {\calO }[0]{\mathcal {O}} \newcommand {\calP }[0]{\mathcal {P}} \newcommand {\calN }[0]{\mathcal {N}} \newcommand {\calR }[0]{\mathcal {R}} \newcommand {\calS }[0]{\mathcal {S}} \newcommand {\calX }[0]{\mathcal {X}} \newcommand {\rmZ }[0]{\mathrm {Z}} \newcommand {\rmC }[0]{\mathrm {C}} \newcommand {\rmH }[0]{\mathrm {H}} \newcommand {\trans }[0]{\mathrm {T}} \newcommand {\Span }[0]{\operatorname {Span}} \newcommand {\Rep }[0]{\operatorname {Rep}} \newcommand {\Vect }[0]{\operatorname {Vec}} \newcommand {\Obj }[0]{\operatorname {Obj}} \newcommand {\Adj }[0]{\operatorname {Adj}} \newcommand {\Aut }[0]{\operatorname {Aut}} \newcommand {\Hom }[0]{\operatorname {Hom}} \newcommand {\End }[0]{\operatorname {End}} \newcommand {\tr }[0]{\operatorname {tr}} \newcommand {\Stab }[0]{\operatorname {Stab}} \newcommand {\FPdim }[0]{\operatorname {FPdim}} \newcommand {\lcm }[0]{\mathrm {l.c.m}} \newcommand {\proj }[0]{\operatorname {proj}} \newcommand {\Repart }[0]{\operatorname {Re}} \newcommand {\Impart }[0]{\operatorname {Im}} \newcommand {\im }[0]{\operatorname {im}} \newcommand {\rk }[0]{\operatorname {rank}} \newcommand {\diag }[0]{\operatorname {diag}} \newcommand {\Zmod }[1]{\Z /#1 \Z } \newcommand {\Reptwo }[0]{\Rep (\Z /2\Z )} \newcommand {\qaH }[0]{\mathrm {H}_{\mathrm {qa}}} \newcommand {\abH }[0]{\mathrm {H}_{\mathrm {ab}}} \newcommand {\qaZ }[0]{\mathrm {Z}_{\mathrm {qa}}} \newcommand {\qaB }[0]{\mathrm {B}_{\mathrm {qa}}} \newcommand {\1}[0]{\mathbf {1}} \newcommand {\Ctimes }[0]{\mathbb {C}^{\times }} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument }$

Row and column operations can be performed using matrix multiplication.

As we have seen, systems of equations—or equivalently matrix equations—are solved by i) forming the ACM associated with the set of equations and ii) applying row operations to the ACM until it is in reduced row echelon form.

It turns out these row operations can be realized by left multiplication by a certain type of matrix, and these matrices have uses beyond that of performing row operations. To explain how matrix multiplication comes into play, let us write $\cal R(_-)$ for a particular row operation on $m\times n$ matrices, so that the given operation is represented by $A\mapsto {\cal R}(A)$ . It turns out that for any of the three types of row operations we have considered above, one has the identity ${\cal R}(A) = {\cal R}(I*A) = {\cal R}(I)*A$ In other words, the row operation ${\cal R}(_-)$ , applied to $A$ , can be realized in terms of left multiplication by the $m\times m$ matrix ${\cal R}(I)$ gotten by applying $\cal R$ to the $m\times m$ identity matrix.

As one would then expect, one has - for each row operation - a corresponding elementary matrix derived from the identity matrix of the appropriate dimension by application of that given operation.

These matrices, and the notation used to define them, can be recorded in an expanded version of the table above in which we indicated the types of operations and their representation:




Type	What it does	Indicated by	Elementary matrix

	Switches
Type I	$i^{th}$ and $j^{th}$	$R_i\leftrightarrow R_j$	${\cal R}(I) = P_{ij}$
	rows

	Multiplies
Type II	$i^{th}$ row	$r\cdot R_i$	${\cal R}(I) = D_i(r)$
	by $r\ne 0$

	Adds
Type III	$a$ times the $i^{th}$ row	$a\cdot R_i$ added to $R_j$	${\cal R}(I) = E_{ji}(a)$
	to the $j^{th}$ row

In an analogous fashion, one can also perform column operations on a matrix. As with row operations there are three types, and each type can be achieved via right multiplication with the corresponding matrix. In other words, if ${\cal C}(_-)$ indicates the given column operation, then for each type one has ${\cal C}(A) = {\cal C}(A*I) = A*{\cal C}(I)$ Denoting the $k^{th}$ column by $C_k$ , we have




Type	What it does	Indicated by	Elementary matrix

	Switches
Type I	$i^{th}$ and $j^{th}$	$C_i\leftrightarrow C_j$	${\cal C}(I) = P_{ij}$
	colmns

	Multiplies
Type II	$i^{th}$ column	$r\cdot C_i$	${\cal C}(I) = D_i(r)$
	by $r\ne 0$

	Adds
Type III	$a$ times the $i^{th}$ column	$a\cdot C_i$ added to $C_j$	${\cal C}(I) = E_{ij}(a)$
	to the $j^{th}$ column

Each elementary matrix is invertible, and of the same type. The following indicates how each elementary matrix behaves under i) inversion and ii) transposition:

$\begin{align} P_{ij}^{-1} = P_{ij},&\qquad P_{ij}^T = P_{ij}\\ D_i(r)^{-1} = D_i(r^{-1}),&\qquad D_i(r)^T = D_i(r)\\ E_{ij}(a)^{-1} = E_{ij}(-a),&\qquad E_{ij}(a)^T = E_{ji}(a) \end{align}$

Elementary matrices are useful in problems where one wants to express the inverse of a matrix explicitly as a product of elementary matrices. We have already seen that a square matrix $A$ is invertible iff is is row equivalent to the identity matrix. By keeping track of the row operations used and then realizing them in terms of left multiplication by elementary matrices, we can write down a product of matrices ending in $A$ that equals $I$ . The product of elementary matrices appearing to the left of $A$ must then be equal to $A^{-1}$ . With such an expression for $A^{-1}$ we can also represent $A$ itself as a product of elementray matrices.

Suppose $A = \begin {bmatrix} 2 & 3\\3 & 5\end {bmatrix}$ . The following (non-unique) sequence of row operations reduces $A$ to $I$ : $\begin {split} \begin {bmatrix} 2 & 3\\3 & 5\end {bmatrix} \xrightarrow {R_2 := R_2 + (-1)*R_1} \begin {bmatrix} 2 & 3\\1 & 2\end {bmatrix} \xrightarrow {R_1 := R_1 + (-2)*R_2} \begin {bmatrix} 0 & -1\\1 & 2 \end {bmatrix}\\ \xrightarrow {R_2 := R_2 + 2*R_1} \begin {bmatrix} 0 & -1\\1 & 0 \end {bmatrix} \xrightarrow {R_1\leftrightarrow R_2}\begin {bmatrix} 1 & 0\\0 & -1 \end {bmatrix}\xrightarrow {(-1)*R_2}\begin {bmatrix} 1 & 0\\0 & 1\end {bmatrix} \end {split}$ Remembering that elementary matrices realize row operations via left-multiplication, transforming the above sequence into a product yields the equation $D_2(-1)*P_{12}*E_{21}(2)*E_{12}(-2)*E_{21}(-1)*A = I$ Setting $B = D_2(-1)*P_{12}*E_{21}(2)*E_{12}(-2)*E_{21}(-1)$ , we see that $B*A = I$ . But we have already seen that this implies $B = A^{-1}$ , the unique inverse of $A$ .

Now if we want to also represent $A$ as a product of elementary matrices, we could do so by the sequence of equalities

$\begin{align*} A &= \big(A^{-1}\big)^{-1}\\ &= \big(D_2(-1)*P_{12}*E_{21}(2)*E_{12}(-2)*E_{21}(-1)\big)^{-1}\\ &= E_{21}(-1)^{-1}*E_{12}(-2)^{-1}*E_{21}(2)^{-1}*P_{12}^{-1}*D_2(-1)^{-1}\\ &= E_{21}(1)*E_{12}(2)*E_{21}(-2)*P_{12}*D_2(-1) \end{align*}$

Suppose $B = \begin {bmatrix} 5 & 1\\4 & 2\end {bmatrix}$ . Find a sequence of row operations that row reduce $B$ to $I$ . Then use this to express both $B^{-1}$ an $B$ as a product of elementary matrices.