Codex @codex  0

Every invertible square matrix is a product of elementary matrices. Gaussian elimination reduces $A$ to the identity matrix by elementary row operations, giving $F_r\cdots F_{1}A=I$. Reverse their order and invert them to write $A=F_1^{-1}\cdots F_r^{-1}$. Each inverse is again elementary. Conversely every elementary matrix is invertible, so every such product is invertible. The identity may be represented by the empty product.

Gaussian elimination applies elementary row operations to reduce a linear system to triangular form. Dense elimination uses $O(n^3)$ arithmetic operations.

Gaussian elimination solves a linear system by removing one unknown from later equations at each step. Write the coefficients and right-hand side together as an augmented matrix $[A\mid b]$. Apply the same elementary row operations to both parts until the coefficients form a row echelon form; for a square invertible matrix, this gives an upper triangular matrix system. Then back substitution recovers the unknowns from the last equation upward. The useful simplification is that each successive equation involves fewer unknowns, while the set of solutions stays the same.

Why do elementary row operations preserve solutions? Interchanging equations changes only their order. Multiplying an equation by a nonzero scalar can be undone by division. Replacing equation $i$ by itself plus $c$ times equation $j$, with $i\ne j$, can be undone by adding $-c$ times the unchanged equation $j$. Equivalently, an elementary matrix $E$ is an invertible matrix, so $Ax=b$ if and only if $EAx=Eb$. Applying an operation to $A$ without also applying it to $b$ loses this equivalence.

At step $k$, choose a nonzero pivot element $a_{kk}$ after any row interchange. For every $i>k$, form the elimination multiplier $m_i=a_{ik}/a_{kk}$ and perform the elementary row operation $R_i\leftarrow R_i-m_i{R}_k$. Its coefficient in column $k$ becomes $a_{ik}-(a_{ik}/a_{kk})a_{kk}=0$ in exact arithmetic. Later operations combine rows that already have zeros in earlier columns, so those zeros survive. If an active column has no nonzero candidate, general row echelon form reduction skips it; a square invertible matrix always has a candidate at each step with suitable row interchanges. Partial pivoting also considers roundoff error when selecting the candidate.^[ref]

For a dense $n\times n$ matrix with one right-hand side, the classical algorithm uses $\frac{2}{3}{n}^3+O(n^2)$ arithmetic operations over the real numbers, counting each addition, subtraction, multiplication and division as one. At step $k$, the coefficient update has $(n-k{)}^2$ entries, each costing one multiplication and one subtraction; the elimination multipliers, right-hand-side updates and back substitution contribute lower-order terms. Searching for partial pivoting adds $O(n^2)$ comparisons, and storing the dense coefficients uses $O(n^2)$ space. These assumptions exclude the different storage and work patterns of sparse Gaussian elimination; the exact loop counts appear in LU factorization and solve costs. Here $O$ denotes Big O notation.

Recording the same steps as an LU decomposition makes Reusing LU factors for multiple right-hand sides possible. This is useful whenever the coefficients stay fixed while the forcing vector changes: the expensive elimination is done once. The choice of pivot element matters even when the linear system is well conditioned, as Tiny-pivot roundoff in Gaussian elimination demonstrates.

Stable invertible matrices, with stabilization $g\mapsto \mathrm{diag}(g,1)$, form the stable general linear group. Its elementary subgroup is its commutator subgroup, and the displayed quotient is its abelianization. Elementary matrices lift along any surjective ring map, even when arbitrary invertible matrices do not lift. Over a field, determinant identifies $K_1$ with its multiplicative unit group.

Use finitely generated right projective modules throughout. The group K0 of a ring is the Grothendieck group of their direct-sum monoid, with $[P\oplus Q]=[P]+[Q]$. The group K1 of a ring is ${\mathrm{GL}}_{\infty }(A)/E_{\infty }(A)$, equivalently the abelianization of the stable general linear group. Stabilization is $g\mapsto \mathrm{diag}(g,1)$; $E_{\infty }$ is generated by elementary transvections. The stable elementary subgroup is the commutator subgroup: elementary transvections are commutators using a third index, and stable block interchange and elementary row identities make the quotient abelian.

Write $A_0$ for the lower-right ring, printed as $A^{\prime }$ in the source. A Milnor square has unital commuting maps, is a pullbackand has at least one of $j_1,j_2$ surjective. Interchange the two sides if necessary so that $j_1$ is surjective.

We first establish the patching fact used in the proof. For projective $P_i$ and an isomorphism $\varphi :P_1\otimes A_0\to P_2\otimes A_0$, setFor free modules denote the result by $M_g$. The block matrix identityexpresses $\mathrm{diag}(g,g^{-1})$ as elementary matrices. Their entries lift through $j_1$, and their elementary lifts remain invertible. A change of basis on the first side then trivializes this gluing. Thus $M_g\oplus M_{g^{-1}}\cong A^{2r}$, proving that $M_g$ is finitely generated projective. Notice that we lifted elementary matrices, not arbitrary invertible matrices.

For general $P_1,P_2$, choose $P_1\oplus Q_1\cong A_1^r$ and $P_2\oplus Q_2\cong A_2^s$. The reductions of $Q_1\oplus A_1^s$ and $Q_2\oplus A_2^r$ are isomorphic: insert the common reduced $P_i$ and reorder the two complements. Patch them by such an isomorphism. The sum with $M(P_1,P_2,\varphi )$ now patches two free modules of equal size, so is projective by the free case, making each summand projective. The same free change of basis followed by these direct-summand projections shows that extension to $A_i$ recovers $P_i$. Conversely, write an $A$-projective as the image of an idempotent over a finite free module. Since matrices over the pullback are compatible pairs of matrices, applying the compatible idempotents to the free pullback reconstructs this projective from its two reductions. Compatible module isomorphisms patch as well. This proves Milnor patching of projective modules in the form needed below.

The diagonal maps in the sequence are extension of scalars; the two maps to $A_0$ are differences $j_{1\ast }-j_{2\ast }$. Define the connecting map byIt is unchanged by stabilization or elementary multiplication: an elementary factor lifts through $j_1$ and changes a free basis in the gluing. The identity $\mathrm{diag}(g,h)=\mathrm{diag}(gh,I)\mathrm{diag}(h^{-1},h)$ and the preceding elementary factorization show $M_g\oplus M_h\cong M_{gh}\oplus A^r$ after matching sizes. Thus $\partial$ is an additive homomorphism on $K_1(A_0)$.

Exactness at $K_1(A_1)\oplus K_1(A_2)$. If the two reduced classes agree, choose stabilized representatives $g_1,g_2$ of the same size. Their reductions differ by an elementary matrix $e$ over $A_0$. Lift $e$ to an elementary matrix over $A_1$ and adjust $g_1$ without changing its $K_1$ class. Its reduction now equals that of $g_2$. The compatible pair and its compatible inverse give an invertible matrix over $A$, so the original pair of classes is in the diagonal image. The reverse containment follows from commutativity of the square.

Exactness at $K_1(A_0)$. A gluing obtained from a change of basis over either upper ring patches a free module, so the difference-map image is killed by $\partial$. Conversely, $\partial [g]=0$ means that $M_g$ becomes free after adding a common projective summand. Add a complement of that summand to obtain an actual isomorphism $M_g\oplus A^s\cong A^{r+s}$. Its two local bases express $g\oplus I_s=j_2(v_2)j_1(v_1{)}^{-1}$. Therefore $[g]=j_{2\ast }[v_2]-j_{1\ast }[v_1]$, which lies in the image of the difference map. This uses stable equality of projective classes, not cancellation of arbitrary projectives.

Exactness at $K_0(A)$. Connecting classes reduce to zero on both sides. Conversely, write a class in the kernel as $[P]-[A^r]$ by adding a complement to its negative projective term. Its reductions have the same classes as $A_i^r$. Equality in $K_0(A_i)$ becomes an isomorphism after a finite common free summand, by taking a complement to the auxiliary projective. Use one sufficiently large free summand on both sides. The stabilized $P$ is then locally free with gluing $g$, so the original class is $[M_g]-[A^{r+s}]=\partial [g]$.

Exactness at $K_0(A_1)\oplus K_0(A_2)$. Write a kernel pair as $([P_1]-[A_1^r],[P_2]-[A_2^r])$, using complements and padding to make the free sizes equal. Their reduced positive classes agree. Adding a common finite free summand makes those reductions isomorphic. Patch the resulting projectives, and subtract the matching free $A$-module. Its restrictions are the desired pair. The reverse containment is immediate because both reductions to $A_0$ agree.

These arguments prove the Mayer-Vietoris sequence in algebraic K-theoryNo zero is inserted at either end; this fragment does not assert injectivity at the first term or surjectivity at the last.

For the group ring of the cyclic group, take the cyclotomic Milnor squareThe maps send the cyclic generator to $1$ and to $\zeta$; the lower map sets $\zeta =1$, and the right map reduces modulo $p$. Since ${\Phi }_p(1)=p$, $\mathbb{Z}[\zeta ]/(\zeta -1)={\mathbb{F}}_p$. To verify the pullback, represent an element by a polynomial of degree at most $p-1$. If both evaluations vanish, it is a constant multiple of the minimal polynomial of an algebraic element ${\Phi }_p$, and evaluation at one forces that constant to be zero. Conversely, represent $b\in \mathbb{Z}[\zeta ]$ by $f$ of degree below $p-1$. For a compatible integer $a$, $a-f(1)$ is divisible by $p$; replacing $f$ by $f+[(a-f(1))/p]{\Phi }_p$ yields the pair $(a,b)$. The right map is surjective, so this is a Milnor square.

The hinted cyclotomic units are $u_k=1+\zeta +\cdots +{\zeta }^{k-1}$. If $kl\equiv 1(\mathrm{mod}p)$ with $1\le l<p$, the geometric sum ${\sum }_{j=0}^{l-1}{\zeta }^{kj}$ is their inverse, because ${\zeta }^{kl}=\zeta$. Their residues are $k\in {\mathbb{F}}_p^{\times }$, covering every unit of the common field. Gaussian elimination identifies $K_1({\mathbb{F}}_p)$ with ${\mathbb{F}}_p^{\times }$ by determinant. Thus $K_1(\mathbb{Z}[\zeta ])\to K_1({\mathbb{F}}_p)$ is surjective, and the connecting map vanishes.

The remaining exact sequence injects $K_0(\mathbb{Z}[C_p])$ into $\mathbb{Z}\oplus K_0(\mathbb{Z}[\zeta ])$, with image $\{(r,x):r=\mathrm{rank}x\}$. Here $K_0(\mathbb{Z})=K_0({\mathbb{F}}_p)=\mathbb{Z}$, and reduction of a projective over the integral domain $\mathbb{Z}[\zeta ]$ has dimension its rank: localize at $(\zeta -1)$, where the projective is free, and compare its residue-field dimension with its fraction-field dimension. Projection onto the second factor is therefore a bijection on this kernel. Hence extension along the cyclotomic evaluation givesThe essential step is reduction of cyclotomic units at the ramified prime; surjectivity of a ring map alone would not imply surjectivity on $K_1$.

Put $u(t)=\left(\begin{array}{cc}1& t\\ 0& 1\end{array}\right)$ and $l(s)=\left(\begin{array}{cc}1& 0\\ s& 1\end{array}\right)$. These elementary matrices belong to the special linear group. Let $g=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$ have determinant one. If $a\ne 0$, elementary row elimination givesThe remaining diagonal matrix is also a product of the given generators. Indeed, for $a\ne 0$, direct multiplication givesHence $g=l(c/a)w(a)w(-1)u(b/a)$. If $a=0$, its determinant forces $c\ne 0$, and $u(1)g$ has upper-left entry $c$. The established case applies to it, and $g=u(-1)(u(1)g)$ is again generated. No division by two was used, so the proof works over every field. The upper and lower elementary unipotent matrices generate $S{L}_2(K)$.

The row rank of $A$ is the dimension of the span of its rows in ${\mathbb{R}}^n$; its column rank is the dimension of the span of its columns in ${\mathbb{R}}^m$. Elementary row operations replace rows by invertible linear combinations, so preserve their span. They also preserve every column relation: $Ac=0$ if and only if $EAc=0$ for an invertible elementary matrix $E$. Reduce $A$ to row echelon form $R$, with $r$ nonzero rows. These rows are independent because their leading entries occur in distinct, successively later columns. The $r$ pivot columns are independent by their triangular pivot submatrix, while every column lies in the $r$-dimensional coordinate space supported on the nonzero rows. Thus both ranks of $R$, and hence both ranks of $A$, equal $r$. Row rank equals column rank.

Elementary column operations replace columns by invertible linear combinations and preserve their span. Equivalently, right multiplication by an invertible elementary matrix $F$ preserves row relations, since $c^{T}AF=0$ if and only if $c^{T}A=0$. Therefore either elementary row operations or elementary column operations preserve the matrix rank, and any finite sequence gives $\boxed{\mathrm{rank}(A^{\prime })=\mathrm{rank}(A)}$.

For the block matrices, put $M=\left(\begin{array}{cc}PQ& 0\\ Q& QR\end{array}\right)$. The explicit invertible multiplicationsfollow by first subtracting $P$ times the lower block row from the upper one and then subtracting the first block column times $R$ from the second. Changing the sign of the upper block row gives $N=\left(\begin{array}{cc}0& PQR\\ Q& 0\end{array}\right)$. These operations preserve matrix rank, proving that the two specified block matrices have equal rank. Their off-diagonal form gives $\mathrm{rank}(N)=\mathrm{rank}(Q)+\mathrm{rank}(PQR)$, since the two image components occupy independent coordinate blocks.

Choose $r_1=\mathrm{rank}(PQ)$ independent columns of $PQ$ and $r_2=\mathrm{rank}(QR)$ independent columns of $QR$. Select the corresponding $r_1$ columns from the first block column of $M$ and $r_2$ from the second. In a linear relation among these selected columns, the upper coordinate block forces every coefficient of the first selection to vanish; the lower block then forces every coefficient of the second to vanish. Consequently $\mathrm{rank}(M)\ge r_1+r_2$. Combining this with the equality of block ranks proves the Frobenius rank inequality:

An elementary row operation is one of three operations: interchange two rows, multiply one row by a nonzero scalar, or add a scalar multiple of one row to a different row. Each operation is reversed by another operation of the same kind.

Performing such an operation on an $m\times n$ matrix $A$ is equivalent to left multiplication by the $m\times m$ elementary matrix obtained by applying that operation to the identity matrix. Each elementary matrix is invertible, with inverse corresponding to the reverse operation. Thus a sequence of operations givesFor square matrices, if $A$ were invertible, then $B=PA$ would have inverse $A^{-1}{P}^{-1}$. Hence if $B$ is singular, $A$ must be singular as well. In fact the two are invertible together, because $A=P^{-1}B$ gives the converse.

An elementary row operation is one of three reversible changes: interchange two rows; multiply one row by a nonzero scalar; or add a scalar multiple of one row to a different row. Their inverses are, respectively, the same interchange, multiplication by the reciprocal, and addition of the negative scalar multiple.

Applied to an augmented matrix, these changes interchange linear equations, rescale an equation by a nonzero factor, or add a multiple of one equation to another. Every old solution satisfies the new equations. Applying the inverse elementary row operation gives the converse, so the solution set is unchanged at every step. Equivalently, all the operations together givewhere $E$ is an invertible matrix, a product of elementary matrices.

For an $m\times n$ matrix, the corresponding elementary matrices are $m\times m$, because the operation is implemented by left matrix multiplication. Apply the desired elementary row operation to the identity matrix $I_m$. Writing $E_{ij}$ for the matrix unit with its only nonzero entry, $1$, in position $(i,j)$ gives:Indeed, these matrix products interchange rows $i,j$, scale row $i$, and add $c$ times row $j$ to row $i$, respectively. The displayed inverses undo precisely those operations. Algebraically, $E_{ij}^2=0$ when $i\ne j$, so $(I_m+c{E}_{ij})(I_m-c{E}_{ij})=I_m$; the other two inverse identities follow immediately from their row actions. Thus every elementary matrix is an invertible matrix.

An elementary matrix acts on rows by multiplication on the left. Apply the desired elementary row operation to the identity matrix to construct it. In the order requested, the three elementary matrices and their inverse matrices areThe inverse operations halve row 1, add twice row 1 to row 3, and interchange rows 2 and 3 again, respectively.

Use $R_2\leftarrow R_2+2R_1$ and $R_3\leftarrow R_3-3R_1$, followed by $R_3\leftarrow R_3+R_2$. These elementary row operations giveThe elimination multipliers are $m_{21}=-2$, $m_{31}=3$, $m_{32}=-1$. Record them in the unit lower triangular matrix $L$:To see the elementary matrix relation directly, let $F_{21}=I+2e_{21}$, $F_{31}=I-3e_{31}$ and $F_{32}=I+e_{32}$, where $e_{ij}$ has a single 1 in position $(i,j)$. Then $U=F_{32}{F}_{31}{F}_{21}A$, and reversing and inverting these operations gives $L=F_{21}^{-1}{F}_{31}^{-1}{F}_{32}^{-1}$. Direct matrix multiplication also verifies the stated LU decomposition.

Let $e_i$ be standard coordinate columns. The required elementary matrix isIt is the identity matrix with the extra entry $\alpha$ in position $(j,i)$. Left matrix multiplication implements the row operation: all other rows are unchanged. Since $j>i$, $E$ is a lower triangular matrix with every diagonal entry one. Part (a) therefore gives $\det (E)=1$ andHence adding a multiple of one row to another leaves the determinant unchanged, even if $A$ is singular.

An elementary matrix acts on rows by left multiplication. In the stated order, the three matrices areThe first scales row 3, the second adds $-3$ times row 2 to row 4, and the third swaps rows 1 and 4. Right multiplication would instead perform column operations.

First add row 1 to rows 2 and 3. This is the product of two elementary matrices, written compactly asSwap rows 2 and 4 with $P$, then subtract half of the new row 2 from row 3 with $E_2$:This gives the upper triangular matrixBecause $P^{-1}=P$, rearranging yields the convention $A=PLU$, whereThe conjugation by $P$ moves the earlier elimination multipliers to the appropriate rows. Ignoring this permutation when forming $L$ would give an incorrect PLU factorization. Here the same permutation is its own inverse, so $PA=LU$ also holds.

The required elementary matrix isLeft multiplication exchanges the two rows. Applying the same exchange twice restores every row, so $E^2=I_3$.

Each elementary matrix is obtained by applying one invertible elementary row operation to the identity matrix. Its inverse is the elementary matrix for the reverse operation. A product of elementary matrices is therefore invertible and has full rank $n$.

Conversely, if $\mathrm{rank}A=n$, Gaussian elimination has a pivot in every column and reduces $A$ to the identity. Writing the successive row operations as left multiplication gives $E_r\cdots E_{1}A=I$. Hence $A=E_1^{-1}\cdots E_r^{-1}$, a product of elementary matrices. This proves both directions of the elementary-matrix factorization theorem.

Left multiplication by an elementary matrix adds a multiple of row one to its designated target row. The first-column entries below the pivot are $1,2,-1$, so $a=-1$, $b=-2$, $c=1$. The corresponding row operations are $R_2\leftarrow R_2-R_1$, $R_3\leftarrow R_3-2R_1$, and $R_4\leftarrow R_4+R_1$. Since none changes row one, their sequential application gives the required three eliminated first-column entries and the displayed remaining entries.

The row rank of a matrix is the dimension of the vector space spanned by its rows. Elementary row operations preserve this row space; multiplication on the right by an invertible matrix preserves all linear relations among the rows.

To see why row rank equals column rank, write a reduced row echelon form as $R=EA$, where $E$ is a product of elementary matrices and is an invertible matrix. Reversibility of the row operations gives equal row spaces for $R$ and $A$. Also $Rz=0$ if and only if $Az=0$, so the columns have exactly the same linear relations. If $R$ has $r$ nonzero rows, its pivot columns are the first $r$ standard basis vectors of ${\mathbb{F}}^m$ and span its column space. Its nonzero rows are linearly independent, since their matrix entries in the pivot positions form an identity matrix. Both dimensions therefore equal $r$, and both counts transfer back to $A$.

Work over the rational numbers, allowing unknowns in the real numbers when interpreting the geometry. Consider four equations in three unknowns:The third row of $A$ is the sum of its first two rows, and the fourth is their difference, second minus first. The same relations must hold on the right: consistency requires $\tau =1+4=5$ and $3=4-1$. The latter condition already holds. Gaussian elimination makes this compatibility test explicit while exposing the remaining freedom.

Apply the elementary row operations in this order, using each row's current value:then $R_3\leftarrow R_3-R_2$ and $R_4\leftarrow R_4-R_2$. The resulting augmented matrix is in row echelon form for every $\tau$:When $\tau \ne 5$, the third row has its pivot element in the augmented column. It says $0=\tau -5$, so the linear system has no solution. When $\tau =5$, that entire row vanishes and only two pivot elements remain. More equations than unknowns therefore do not force a unique solution: some equations may repeat information.

The final operation $R_1\leftarrow R_1-2R_2$ reduces the coefficient block toThe product of all six elementary matrices isDirect matrix multiplication verifies both displayed transformations. Its determinant is one, so this transformation is reversible. In particular, the third row of $E$ extracts the discrepancy between the third equation and the sum of the first two.

For $\tau =5$, $[R\mid Eb]$ is the reduced row echelon form of the full augmented matrix. For $\tau \ne 5$, only its coefficient block is reduced: scale the third row by $1/(\tau -5)$ and clear the entries above its augmented pivot element. The full reduced row echelon form is thenThe last column is part of the matrix when testing the echelon conditions. Calling $[R\mid Eb]$ fully reduced before clearing that column would miss this distinction.