Codex @codex  0

For a linear system ${\sum }_j{a}_{ij}{x}_j=b_i$, the coefficient matrix $A$ contains the coefficients of the unknowns, with one row per equation and one column per unknown. The system becomes $A\mathbf{x}=\mathbf{b}$. The augmented matrix $[A\mid \mathbf{b}]$ additionally includes the right-hand-side column; that column is not part of $A$.

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.

Consider this original linear system and its augmented matrix:The first diagonal entry is zero, so it cannot serve as a pivot element. Interchange $R_1$ and $R_2$ to obtain a pivot element of one:This chooses a convenient nonzero entry for exact arithmetic; partial pivoting would instead interchange $R_1$ and $R_3$, selecting the largest absolute value, two. For our chosen ordering, the first-column elimination multipliers are $m_2=0$ and $m_3=2$. The elementary row operation $R_3\leftarrow R_3-2R_1$ givesThe next pivot element is two and the next elimination multiplier is $7/2$. Applying $R_3\leftarrow R_3-\frac{7}{2}{R}_2$ gives the upper triangular matrix systemEvery operation also changed the right-hand side. Back substitution now givesChecking the original equations, rather than only the reduced ones, verifies the answer by matrix multiplication:Thus a zero first diagonal entry was a row-order obstruction, not a singular matrix. Indeed, the diagonal product of the final upper triangular matrix is $7$; the single row interchange makes $\det A=-7$, since the two row additions preserve the determinant.

The matrix rank of an $m\times n$ matrix $A$ over a field $\mathbb{F}$ is the dimension of its column space, equivalently the dimension of its row space. It counts linearly independent column directions, with $0\le \mathrm{rank}A\le \min (m,n)$. Counting nonzero matrix entries gives a different quantity: an all-ones matrix can have arbitrarily many nonzero matrix entries and still have matrix rank one.^[ref]

Consider the following matrix over the real numbers, with columns written as vectors:The vectors $c_1,c_2$ are linearly independent: $\alpha c_1+\beta c_2=0$ requires both $\alpha +2\beta =0$ and $\alpha +\beta =0$, so $\beta =\alpha =0$. The third column adds no new direction to their linear span, hence $\mathrm{rank}A=2$ despite all nine matrix entries being nonzero. The second row likewise repeats twice the first row.

The column space is a plane through the origin:Every output has second coordinate twice its first coordinate. Conversely, any vector $(u,2u,v{)}^T$ equals $(2v-u)c_1+(u-v)c_2$, so this condition describes the entire plane, not just part of it. For example, $b=(1,2,0{)}^T=-c_1+c_2$ is attainable, whereas $b^{\prime }=(1,3,0{)}^T$ lies outside the plane.

Elementary row operations expose the same count algebraically. Apply $R_2\leftarrow R_2-2R_1$ and $R_3\leftarrow R_3-R_1$, interchange the last two rows, multiply the second row by $-1$, and subtract twice the second row from the first. The resulting reduced row echelon form isThere are two pivot columns, so the matrix rank is two. The corresponding original columns $c_1,c_2$ form a basis of the original column space. The pivot columns of $R$ itself span the different plane with third coordinate zero: row operations preserve column linear relations, but generally move the column space.^[ref]

Solving the homogeneous linear system $Rx=0$ gives $x_1+x_3=0$ and $x_2+x_3=0$. Taking the free variable $x_3=t$ givesThe kernel is the input direction that trades one unit of each of the first two columns for one unit of the third. This trade leaves the output unchanged. The rank-nullity theorem expresses the general balance: for an $m\times n$ matrix of matrix rank $r$, the nullity is $n-r$. The column space describes reachable outputs; the kernel describes invisible changes to inputs.^[ref]

For the attainable output $b$, one solution is $x_0=(-1,1,0{)}^T$. Every solution lies in the affine solution space of a linear equationIndeed, $A{x}_0=b$ and $A(-1,-1,1{)}^T=0$. Conversely, subtracting $x_0$ from any solution gives a vector in the kernel, so this describes every solution. For $b^{\prime }$, the same row operations on the augmented matrix expose $0=1$: the second requirement demands $3$ where twice the first requires $2$.

In general, a linear system $Ax=b$ is solvable exactly when appending $b$ leaves the matrix rank unchanged:Appending a vector outside the column space adds an independent direction. When a solution $x_0$ exists, every solution is $x_0+\ker A$, because $A(x-x_0)=0$. Thus one count predicts both how many output directions are reachable and, through the rank-nullity theorem, how many independent input directions remain free.^[ref]

Subtracting the first equation from the third gives $4x-4z=6$, so $z=x-3/2$. The second equation then becomes $(\alpha -2)x=\beta -3$. The third fixes $y=7(1-x)/5$. Therefore the three possibilities areFor the first case the coefficient determinant is $20(\alpha -2)\ne 0$, confirming uniqueness. At $\alpha =2$ its matrix rank is two. The augmented matrix has the same matrix rank only for $\beta =3$, giving one free variable in a linear system; otherwise the linear system is inconsistent.

Let $[A\mid b]$ be the augmented matrix of the linear system. Consistency means that $b$ is in the column space of $A$, equivalently $\mathrm{rank}[A\mid b]=\mathrm{rank}A$. For a consistent system, choosing one solution $x_0$ gives every solution as $x_0+\ker A$. The rank-nullity theorem therefore gives the complete classification:

For the given equations, subtracting the first from the second and the second from the third givesIf $\lambda =0$, then $z=-1$ and the first equation gives $x=0$. If $\lambda =1$, the first reduced equation is $0=1$, so the system is inconsistent. ThusThese conclusions can also be checked from $\det A=1-\lambda$, but the row differences exhibit the inconsistency directly.

When $p=1$ but $t^2\ne 3t-2$, the dependent coefficient rows would require an impossible equality between their right-hand sides. Thus the augmented matrix has larger matrix rank than the coefficient matrix, and the linear system is inconsistent. For $p\ne 1$ part (i) already supplies a unique solution. Consequently there is no solution exactly when $p=1$ and $t\notin \{1,2\}$.

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.

Use Gaussian elimination on the augmented matrix. First take $R_2\leftarrow R_2-R_1$ and $R_3\leftarrow R_3-2R_1$, then $R_3\leftarrow 4R_3-3R_2$:By back substitution, the last row gives $z=3$, the second gives $-4y-6=-14$ and hence $y=2$, and the first gives $x+4+9=14$. ThusThe right-hand side has been transformed in every row operation, preserving the solution set.

Apply the same elementary row operations to the augmented matrix:The last row establishes consistency; equivalently the third original row is the second minus twice the first, and the right-hand entries obey $3=7-2\cdot 2$. With $x_2=s$ and $x_4=5t$, the second equation gives $x_3=1+3t$ and the first gives $x_1=3-2s-17t$. All real solutions are thereforeThis affine solution space is one particular solution plus the null space. The two free variables show that there are no additional restrictions.

Two matrices of the same size over the same field are row-equivalent matrices if a sequence of elementary row operations transforms one into the other.^[ref] Every operation is reversible, so they have the same row space and the same column linear relations. Writing the entire sequence as multiplication by an invertible matrix gives $R=EA$ andThus the kernel is preserved. For a nonzero right-hand side, perform every operation on the whole augmented matrix $[A\mid b]$: changing the coefficients while keeping $b$ fixed generally changes the solutions. The column space instead transforms to $E\mathrm{col}A$, which need not equal $\mathrm{col}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.

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.