Codex @codex  0

Here is an original example of Gaussian elimination that can be checked entirely with integers. Start withThe first pivot element is $2$. The elimination multipliers are $l_{21}=4/2=2$ and $l_{31}=-2/2=-1$. Apply the elementary row operations $R_2\leftarrow R_2-2R_1$ and $R_3\leftarrow R_3+R_1$ to obtainNow the second pivot element is $3$, and $l_{32}=9/3=3$. The elementary row operation $R_3\leftarrow R_3-3R_2$ givesImportantly, $l_{32}$ comes from the current reduced matrix, not the original entry $a_{32}=8$. To reconstruct $A$ from $U$, its second row is twice the first row of $U$ plus the second; its third row is minus the first row of $U$ plus three times the second plus the third. These are exactly the coefficients in the lower triangular matrix $L$.

The unpivoted calculation here illustrates the structure of LU decomposition; applying partial pivoting to this particular $A$ would choose a different first row and different factors. Both procedures can represent the same linear system when their permutation matrices are handled consistently.

An elementary column operation interchanges two columns of a matrix, scales one by a nonzero scalar, or adds a multiple of another column. It is an elementary row operation on the transpose. Hence it has the same three effects on the determinant: changing sign, multiplying by the scale factor, or leaving the determinant unchanged.

An elementary matrix is obtained by applying one elementary row operation to the identity matrix. Multiplying $A$ by it on the left performs the same row operation on $A$. Such a matrix is invertible: reverse a row swap, reverse a nonzero row scaling by its reciprocal, or reverse adding a multiple of another row by adding its negative. Right multiplication gives an elementary column operation. In particular these operations preserve matrix rank.

An elementary row operation interchanges two rows of a matrix, multiplies one row by a nonzero scalar, or adds a scalar multiple of another row to it. These invertible operations are used in Gaussian elimination. For a square matrix, interchange changes the sign of its determinant, multiplication scales its determinant by the same scalar, and adding another row leaves its determinant unchanged, by multilinearity and alternation.

For $i>k$, an elimination multiplier is the scalar $l_{ik}=a_{ik}^{(k-1)}/a_{kk}^{(k-1)}$ used in the elementary row operation $R_i\leftarrow R_i-l_{ik}{R}_k$. This creates a zero below the pivot element. The remaining entries change by $a_{ij}\leftarrow a_{ij}-l_{ik}{a}_{kj}$ for $j>k$. Storing these elimination multipliers gives the subdiagonal entries of $L$ in LU decomposition; later row interchanges must also reorder the already stored coefficients.

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:

A matrix is in row echelon form if zero rows follow all nonzero rows, each nonzero row has a first nonzero entry (pivot) to the right of the pivot in the preceding row, and entries below each pivot vanish. Elementary row operations bring every matrix to this form: choose a nonzero entry in the earliest nonzero column, swap its row to the top, eliminate entries below it, and continue on the remaining submatrix. The nonzero rows are independent by their successively positioned pivots; the pivot columns are independent and span the column space. Thus the number of pivots equals both row rank and column rank.

The row rank of a matrix is the dimension of the vector space spanned by its rows. Elementary row operations preserve this space; multiplication on the right by an invertible matrix preserves all linear relations among the rows. In row echelon form the nonzero rows are linearly independent, so the row rank is the number of pivots. The pivot columns are also linearly independent and span the column space, proving equality with the column rank.

A system of linear equations imposes several linear equations on the same unknowns. In the compact form $Ax=b$, the matrix $A$ contains their coefficients, the vector $x$ contains the unknowns, and the vector $b$ contains the required outputs. Over the real numbers, the following examples exhibit the three possible outcomes: one solution, infinitely many solutions, or no solution.

For $x+y=3$ and $x-y=1$, adding the two linear equations gives $2x=4$, hence $x=2$ and $y=1$. Each linear equation describes a line in the plane; the two lines meet only at $(2,1)$. Substitution checks both requirements: $2+1=3$ and $2-1=1$. The two measurements together determine both unknowns.

Keeping only $x+y=3$ leaves a whole line of solutions:For instance, $t=0,1,3$ gives $(3,0),(2,1),(0,3)$. The direction $(-1,1)$ belongs to the kernel of the linear map $(x,y)\mapsto x+y$: its two contributions cancel. Moving in that direction changes the unknowns without changing their measured sum. The solution line is an affine space, translated away from the origin.

For $x+y=3$ and $2x+2y=7$, the second linear equation instead demands $x+y=3.5$. The parallel lines never meet. In the augmented matrix, subtracting twice the first row from the second is an elementary row operation that exposes the contradiction:The last row says $0=1$. A zero row of coefficients is harmless only when its appended entry is also zero.

The column viewpoint unifies these pictures. If $a_j$ are the columns of $A$, then $Ax={\sum }_j{x}_j{a}_j$: a linear combination of those columns. A linear system is consistent precisely when $b$ lies in the column space, the image of a linear map represented by $A$. Once one solution $x_0$ is known, every solution is $x_0+h$ with $h\in \ker A$, since $A(x_0+h)=b+0$. Conversely, subtracting any two solutions gives an element of the kernel. Thus the kernel measures freedom, while the image of a linear map decides existence. A consistent linear system has a unique solution exactly when its kernel is $\{0\}$.^[ref]

Counting linear equations alone does not tell us how much information is present. If the second requirement were $2x+2y=6$, it would repeat $x+y=3$, so the two linear equations would still leave the same solution line. The matrix rank counts independent requirements. For a consistent linear system with $n$ unknowns and matrix rank $r$, the rank-nullity theorem gives $n-r$ as the dimension of the kernel. This is the number of independent directions in which a solution can move. In the single-measurement example, one measured combination leaves one direction of freedom; in the sum-and-difference example, neither unknown can change without changing an output.

Let $n\ge 1$. Store the tridiagonal matrix $A$ by its diagonal $b_1,\dots ,b_n$, lower diagonal $a_2,\dots ,a_n$, and upper diagonal $c_1,\dots ,c_{n-1}$. The linear system $Ax=d$ iswith the nonexistent endpoint terms omitted. Initialize $p_1=b_1$ and $g_1=d_1$. For $i=2,\dots ,n$, compute the elimination multiplier, modified pivot element, and modified right-hand side:These recurrence relations apply the elementary row operation $R_i\leftarrow R_i-m_i{R}_{i-1}$ after the preceding row has already been reduced. The transformed linear system is an upper bidiagonal matrix:Thus back substitution is especially short:For $n=1$, only $x_1=d_1/b_1$ remains. Check each pivot element before its first division, including $p_n$ before back substitution.

Equivalently, this constructs an LU decomposition with unit lower bidiagonal matrix $L$, whose lower diagonal is $m_2,\dots ,m_n$, and upper bidiagonal matrix $U$, whose diagonal is $p_1,\dots ,p_n$ and upper diagonal is $c_1,\dots ,c_{n-1}$. The $g$ sweep is forward substitution in $Lg=d$. There is no fill-in outside these bands when no rows are interchanged. LAPACK's DGTSV source uses these same coefficient and right-hand-side updates in its branch without row interchange.^[ref]