Codex @codex  0

An affine map combines a linear map with a translation. After choosing coordinate origins, it has the form $T:{\mathbb{R}}^p\to {\mathbb{R}}^q$, $T(x)=Mx+b$, where the $q\times p$ matrix $M$ is its linear part of an affine map and $b$ is a fixed vector. Equivalently, it preserves every affine combination. ^[ref]

An original planar example isIt stretches horizontally, applies a shear mapping, and then translates. The vertices $A=(0,0)$, $B=(2,0)$ and $C=(0,2)$ become $A^{\prime }=(1,-2)$, $B^{\prime }=(5,-2)$ and $C^{\prime }=(3,0)$. A square grid becomes a grid of parallelograms; straight edges and their weighted points still fit together.

This map is not a linear map with respect to the displayed origins, because $T(0,0)=(1,-2)$ rather than zero. It also is not a Euclidean similarity: $AB$ has length $2$ and $A^{\prime }{B}^{\prime }$ has length $4$, while the right angle at $A$ becomes $45^{\circ }$. Its determinant is $2$, so it doubles planar area. These metric changes explain why affine geometry studies straightness, incidence and weighted points rather than treating every transformation as an isometry.

The linear part is an invertible matrix, giving the concise inverse $T^{-1}(u,v)=((u-v-3)/2,v+2)$. More generally an affine map is bijective exactly when its linear part of an affine map is bijective. Between equal finite-dimensional spaces, this means an invertible matrix; the translation cannot repair a loss of rank of a linear map.

A matrix whose columns are the coordinate vectors of an ordered basis in a fixed reference basis. It is an invertible matrix, and multiplication by it converts coordinates in the column basis to the reference coordinates: $v=B[v{]}_B$. For a real inner product space with orthonormal reference basis, its Gram matrix is $B^{T}B$, and its reciprocal basis has basis matrix $B^{-T}$.

Write a linear system as $Ax+By=f$ and $Cx+Dy=g$, with $A$ an invertible matrix. Solving the first equation for $x$ and substituting in the second givesThus the Schur complement is the coefficient matrix remaining after the $x$ variables have been eliminated. When it is an invertible matrix, solve the reduced linear system for $y$ and recover $x$. In computation, expressions such as $A^{-1}B$ mean solving with each column of $B$, using the same LU decomposition or Cholesky decomposition when applicable.

For the example under block matrix inverse and right-hand side $(3,1,4{)}^T$, take $f=(3,1{)}^T$ and $g=4$. Since $C{A}^{-1}f=13/6$, the reduced equation is $(19/6)y=11/6$. Back substitution givesThe original equations return $3$, $1$ and $4$, respectively. The reduction retained the influence of $x_1,x_2$ on $y$ through the correction $C{A}^{-1}B$.

A short proof outline also explains whether $M$ is an invertible matrix: the exact matrix factorizationhas invertible matrices on the outside. Therefore $M$ is an invertible matrix precisely when the central block diagonal matrix is one. Reversing the factors gives the block matrix inverse, while taking determinants gives the Schur complement determinant identity.

A block matrix inverse expresses the matrix inverse in terms of smaller matrices. Partition a square matrix over a field asIf $A$ is an invertible matrix, define its Schur complement $S=D-C{A}^{-1}B$. Then $M$ is an invertible matrix exactly when $S$ is an invertible matrix, andThe order of the matrix products matters. In particular, the lower-right block is $S^{-1}$, rather than generally $D^{-1}$: the coupling through $B$ and $C$ changes the response.^[ref]

For an original example, takeThe Schur complement is $S=5-1/2-4/3=19/6$. Substitution gives the concise answerMultiplying in either order gives the identity matrix; the lower-right entry is $6/19$, whereas $D^{-1}=1/5$. The difference records the feedback through the two eliminated variables.

Often the desired output is a solution of a linear system, rather than every entry of a matrix inverse. Block elimination solves with $A$ and then with $S$, recovering the eliminated variables by back substitution. Reusing an LU decomposition of $A$ avoids explicitly forming $A^{-1}$. A favourable block diagonal matrix or tridiagonal matrix block can make this useful; merely partitioning an unstructured dense matrix does not guarantee a faster solve.^[ref]

Keep the same origin and the same vector $p=(2,1{)}^T$, but use the nonperpendicular basis vectors $b_1=(1,0{)}^T$ and $b_2=(1,1{)}^T$. They form a basis because the column matrix $B$ has nonzero determinant:The reconstruction is $p=b_1+b_2$. Its coordinates are read along lines parallel to the other axis, producing a parallelogram. These lines need not be perpendicular to the axis being measured. In contrast, the dot products are $p\cdot b_1=2$ and $p\cdot b_2=3$; treating those as coordinates would reconstruct $2b_1+3b_2=(5,3{)}^T$, a different vector.

The dual basis supplies the right measuring rules for any basis.^[ref] Here these coordinate functionals are $b_1^{\ast }(x,y)=x-y$ and $b_2^{\ast }(x,y)=y$, the rows of $B^{-1}$. They give $b_1^{\ast }(p)=b_2^{\ast }(p)=1$. Equivalently, their representing vectors $d_1=(1,-1{)}^T$, $d_2=(0,1{)}^T$ satisfy $d_i\cdot b_j={\delta }_{ij}$ and extract the coordinates as $d_i\cdot p$. These are Riesz dual basis in an inner product space representatives, rather than the original basis vectors.

The Gram matrix records how the nonperpendicular directions interact:For any real basis represented by a square invertible matrix $B$, writing $p=Bc$ gives these identities immediately. One can recover the coordinates either as $c=B^{-1}p$ or by solving $Gc=B^{T}p$. In this example, if $c=(a,b{)}^T$, the squared norm is $a^2+2ab+2b^2$, not $a^2+b^2$. Oblique coordinates remain useful when natural directions are not perpendicular, but the Gram matrix must accompany them when computing lengths or dot products.

Fix the convention: the columns of the change-of-basis matrix $P$ are the new basis vectors written in the old basis. Thus $P$ converts new coordinate vectors into old ones; its matrix inverse converts old coordinate vectors into new ones. For the preceding basis,Its determinant is $-2$, so $P$ is an invertible matrix. Checking which direction $P$ converts is essential: different books may call either $P$ or $P^{-1}$ the change-of-basis matrix.

For a linear operator, convert the input into the old basis, apply the old matrix, and convert the output back. Reading that sequence from right to left givesFor example, let the old diagonal matrix stretch horizontal components by $2$ and vertical components by $3$. ThenThe output represents $2u+2v=(4,0)$, just as $A_{\mathrm{old}}(2,0{)}^T=(4,0{)}^T$. The matrices look different because their bases differ, but they encode the same linear operator. This relation is called matrix similarity; it preserves the underlying action.^[ref]

For any real vector $u$, a Cholesky decomposition gives the quadratic form identitySince $L$ is an invertible matrix, this squared Euclidean norm is positive whenever $u\ne 0$. The factorization thus certifies positive definiteness and gives coordinates in which the quadratic form is a sum of ordinary squares. For the matrix above,The level set $u^{T}Au=1$ is an ellipse; the linear map $z=L^{T}u$ sends it to the unit circle. The points $u=(1/2,0{)}^T$ and $u=(-1/4,1/2{)}^T$ go to $(1,0{)}^T$ and $(0,1{)}^T$, respectively.

The same factor works in the reverse direction for Gaussian random vectors. If $Z$ has independent unit-variance, zero-mean Gaussian random variables as coordinates, $X=LZ$ has covariance matrix $L{L}^T=A$. In this example $X_1=2Z_1$ and $X_2=Z_1+2Z_2$: their variances are $4$ and $5$, while their covariance is $2$. This is a concrete way to generate specified correlations from independent draws.

A triangular factor is not generally a square root of a matrix in the sense $B^2=A$. Here $L^2=\left(\begin{array}{cc}4& 0\\ 4& 4\end{array}\right)\ne A$. The Cholesky decomposition uses the product with the transpose, which is also what makes the quadratic form a squared Euclidean norm.

An invertible matrix need not have an invertible chosen diagonal block. For example,has singular matrices as both one-by-one diagonal blocks. Neither diagonal-block formula applies in that partition. Interchanging the two rows produces the identity matrix and a usable pivot element. This is why a failed block pivot is not proof that the full matrix is a singular matrix; Pivoted LU decomposition changes the order before eliminating.

Conversely, invertible diagonal blocks do not suffice: $M=\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$ has $A=D=1$ but Schur complement $S=0$, so it is a singular matrix. Both hypotheses in the block matrix inverse formula have work to do.

The column rank of a matrix is the dimension of its image of a linear map, equivalently the dimension of the linear span of its columns. Multiplication on the left by an invertible matrix preserves all column linear relations, and elementary column operations preserve their linear span. In row echelon form the pivot columns form a basis of the column space. Its dimension equals the number of nonzero rows, and hence the row rank.

For the cubic polynomial, an oriented, normalized tangent vector isIts Euclidean norm is one and $DF(z_k)t_k=0$. The sign here follows increasing $x$; for a general solution branch, choose the sign of each new tangent vector so its dot product with the previous one is positive. First predict $z_{\mathrm{p}}=z_k+h{t}_k$, then apply Newton method starting at $z_{\mathrm{p}}$ toThe second equation keeps the correction on the transverse line in this two-dimensional example; in higher dimensions it is a hyperplane. Solving the linear system $DH(z^{(j)})\delta z=-H(z^{(j)})$ and updating $z^{(j+1)}=z^{(j)}+\delta z$ corrects both coordinates together.

This step gives $z_{\mathrm{p}}\approx (0.617556,0.424641)$ and $z_{k+1}\approx (0.635532,0.378840)$. Check both equations: the solution must satisfy $x^3-x+\lambda =0$ and $t_k^{\mathsf{T}}(z-z_{\mathrm{p}})=0$. Checking only the first could accept any point on the solution branch. The new $x$ exceeds $1/\sqrt{3}$, so the step crosses the continuation fold, even though the predictor's $\lambda$ exceeds $2/(3\sqrt{3})$.

At the seed, set $a=3x_k^2-1$. The determinant of the correction Jacobian matrix with the exact unit vector above isAt either continuation fold, $a=0$, $t_k=(1,0)$ and $DH(z_k)=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$: the correction remains invertible. More generally, if $DF$ has full rank and a one-dimensional kernel spanned by $t_k$, adding $t_k^{\mathsf{T}}$ gives an invertible matrix, since a vector annihilated by both rows must be zero. This is a local argument; the old transverse hyperplane need not work arbitrarily far along the curve. Reduce $h$ and retry when correction fails, and check the equations and orientation after successful steps. Scaling state and parameter coordinates also matters, because it changes the Euclidean norm used to normalize the tangent vector.

// Target: analysis.bigb

Let the columns of an invertible matrix $B$ be a new basis expressed in the old basis. The same vector has old coordinate vector $x$ and new coordinate vector $x^{\prime }=B^{-1}x$. If a covector has old row $\ell$, its new row is ${\ell }^{\prime }=\ell B$, sinceThus the scalar dual pairing stays unchanged. If covector coefficients are stored as a column $c={\ell }^T$, their new column is $c^{\prime }=B^{T}c$; this is the inverse transpose of the transformation $x\mapsto B^{-1}x$ on vector coordinates. These conventions express the covariance and contravariance of vectors. ^[ref].

For the basis $b_1=(1,0)$, $b_2=(1,1)$,The linear functional $\phi (x,y)=2x-y$ has rows $\ell =\left(\begin{array}{cc}2& -1\end{array}\right)$ and ${\ell }^{\prime }=\left(\begin{array}{cc}2& 1\end{array}\right)$. Both calculations give five: $2\cdot 3-1\cdot 1=2\cdot 2+1\cdot 1$. Changing the basis changes the descriptions, not the measured value.

For four distinct projective points on the complex projective line, use the conventionwhere $[p_i,p_j]$ is the determinant of chosen representative vectors. Rescaling any representative cancels, and applying an invertible matrix multiplies every bracket by its determinant, which also cancels. Thus the expression is a projective invariant. The projective general linear group action on the projective line has a unique element $T$ taking the first three points to $\infty ,0,1$. In those coordinates the displayed expression is exactly $T(P_3)$. Consequently the cross-ratio completely determines the orbit of the ordered quadruple under the projective linear group. Its value lies in $\mathbb{C}\setminus \{0,1\}$.

A cube root of a matrix $A$ is a square matrix $B$ of the same size over the specified field satisfying $B^3=A$. Every complex invertible matrix has one: put it in Jordan normal form, choose a scalar cube root of each nonzero eigenvalue, and apply the truncated binomial cube root of the identity plus a nilpotent matrix on each block. The Nilpotent Jordan block $J_3(0)$ has none, even though its square is nonzero. If $B^3=J_3(0)$, then $B^9=0$, making $B$ a nilpotent matrix of size three; the Cayley-Hamilton theorem then gives $B^3=0$, a contradiction.

The determinant assigns a scalar to a square matrix. For a linear map on the real plane, it measures signed area scaling: its absolute value tells how much area grows, and its sign records whether the orientation of a vector space is preserved or reversed. In three dimensions, the same idea measures signed volume. Over a field, a square matrix is an invertible matrix exactly when its determinant is nonzero. These are two views of one phenomenon: losing an independent direction collapses full-dimensional volume and makes the original input impossible to recover uniquely.^[ref]

Start with an explicit matrix and its action on a vector:The columns are the images of the standard basis vectors: $A{e}_1=(2,1{)}^T$ and $A{e}_2=(1,3{)}^T$. Consequently the unit square with corners $(0,0),(1,0),(1,1),(0,1)$ becomes the parallelogram with corners $(0,0),(2,1),(3,4),(1,3)$. Its area is five. Every small patch of this square undergoes the same linear map, so the factor describes the whole deformation, rather than just one specially chosen boundary. The matrix mixes horizontal and vertical components, but its determinant compresses that combined effect into one area factor.^[ref]

Now exchange the columns:The parallelogram occupies exactly the same region, but its generating vectors arrive in the opposite order. Moving from the first column to the second now turns clockwise rather than counterclockwise. Ordinary area remains five; the oriented volume in two dimensions changes sign. A negative determinant therefore signals reversed orientation of a vector space, not a negative amount of material. Keeping the sign makes successive reversals calculable: two reversals restore the original orientation of a vector space.

Compare a singular matrix:Its columns are linearly dependent: the second is twice the first. The unit square collapses onto the segment from $(0,0)$ to $(3,6)$, which has zero area despite nonzero length. Since $C(-2,1{)}^T=0$, the kernel of a linear map contains a nonzero vector; inputs differing by that vector have identical outputs. The collapsed picture explains why an inverse matrix cannot exist.

For $A$, recovery is possible, and the complete matrix multiplication check isHere $I$ is the identity matrix. The inverse matrix restores the original square, shrinking its area by $1/5$. Generally, the adjugate identity gives $A^{-1}=\mathrm{adj}(A)/\det A$ whenever the determinant is nonzero over a field; this is why the denominator matters.^[ref]

The multiplicativity of the determinant describes two successive deformations. Matrix multiplication means that $AB$ applies $B$ first, then $A$. TakeThe first linear map doubles area; the second multiplies the resulting area by five. Thus the unit square passes through areas $1,2,10$, with the last parallelogram bounded by $(0,0),(2,1),(4,7),(2,6)$. Direct calculation agrees:This explains physically why area factors multiply instead of adding. The general identity holds for square matrices of the same size, including singular matrices. If either stage loses a direction, later processing cannot recover the discarded information.^[ref]

The same interpretation works in three dimensions without drawing a new picture. The diagonal matrixsends the unit cube to a rectangular box with side lengths two, three, and one. Its ordinary volume is six. The minus sign comes from reversing the third direction, so the oriented volume is minus six. Replacing the last diagonal entry by zero flattens the cube into a planar region: its area may be positive, but its three-dimensional volume is zero. This distinction matters whenever a linear map changes shape: the determinant measures size in the full input dimension, rather than the size of whichever lower-dimensional object remains.

The determinant measures neither trace nor perimeter. For $A$, the trace happens also to be five, but the identity matrix in two dimensions has trace two and determinant one. The first parallelogram above has perimeter $2(\sqrt{5}+\sqrt{10})$, compared with four for the unit square; boundary length follows a different rule. Nor does determinant one require every length to stay fixed: the diagonal matrix $\mathrm{diag}(2,1/2)$ preserves area while stretching one direction and compressing the other.

These properties make the determinant useful when coordinates obscure what a deformation does. A nonzero determinant certifies that linearly independent input directions remain distinguishable; its magnitude counts the area or volume represented by a transformed cell. That second role reappears in the change of variables formula, where the Jacobian determinant corrects the sizes of small cells. Signed volume also separates a deformation that reverses the orientation of a vector space from one that merely stretches it, even when both give identical ordinary volume factors.^[ref]

For general $n$, regard the columns $v_1,\dots ,v_n$ as ordered arguments. The determinant is the unique alternating multilinear map to the scalar field normalized by $\det I=1$. The multilinearity of the determinant means linearity in each column separately, with all others held fixed:Alternation means equal columns give zero; exchanging columns negates the result. Normalization sets the oriented volume of the standard basis to one. These properties also hold in rows. For real three-dimensional columns, their determinant is the scalar triple product, and its absolute value is the enclosed volume. Over other fields, the algebraic definition still works even without a geometric notion of positive volume.^[ref]

Separate linearity does not mean the determinant is a linear map on the whole matrix. Scaling every column of an $n$-by-$n$ matrix by $t$ gives $\det (tA)=t^n\det A$. For our two-dimensional example, $\det (2A)=4\det A=20$: doubling both directions quadruples area. The power records how many independent directions are being scaled together.

The properties suggest practical computations. Adding a multiple of one column to another preserves the determinant: the extra term has repeated columns and vanishes. This is the algebra behind an area-preserving shear mapping. Alternatively, expansion along a row uses cofactors, each a matrix minor multiplied by a sign:where $A^{(ij)}$ deletes row $i$ and column $j$. The Leibniz formula for determinants supplies the general entry formula. Both calculations encode the same geometric invariant; the defining properties explain their structure without requiring memorization of a separate recipe for every size.^[ref]

A finite-dimensional linear operator is diagonalizable over a specified field when it has an eigenbasis. Equivalently, its matrix $A$ admitswhere $P$ is an invertible matrix whose columns are eigenvectors, and $D$ is a diagonal matrix of the corresponding eigenvalues. This change of basis reveals a linear map as independent one-dimensional scalings. The matrix may look coupled in the original coordinates, but each coordinate in the eigenbasis evolves on its own.

For the symmetric matrix $A=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$ computed in eigenvector, takeThen $AP=PD$, hence $P^{-1}AP=D$. The orthonormal basis version is $Q=P/\sqrt{2}$, an orthogonal matrix satisfying $Q^{T}AQ=D$. Every real symmetric matrix has an orthonormal eigenbasis by the spectral theorem; a general diagonalizable matrix need not have orthogonal eigenvectors.

The immediate payoff is repeated application: adjacent factors $P^{-1}P$ cancel, giving $A^n=P{D}^n{P}^{-1}$. In this example,The component in $E_3$ grows while the component in $E_1$ stays fixed. After division by its Euclidean norm, this particular sequence approaches $(1,1{)}^T/\sqrt{2}$. This is the mechanism behind the power method; an initial vector entirely in $E_1$ would stay there and never find the dominant eigenvalue $3$.

Two different obstructions deserve comparison. The planar rotation $R$ in eigenvector is diagonalizable over $\mathbb{C}$ but not over $\mathbb{R}$, because its eigenvalues are $i$ and $-i$. By contrast, the shear mappinghas only $\lambda =1$, of algebraic multiplicity two, and $E_1=\mathrm{span}\{(1,0{)}^T\}$, of geometric multiplicity one. There is no second independent eigenvector, even over $\mathbb{C}$. This is a defective matrix, already a two-dimensional Jordan block. Its powers areThus even though both eigenvalues are one, repeated application can produce growth. Eigenvalues alone miss the coupling recorded by a Jordan block. A repeated eigenvalue is harmless when it has enough independent eigenvectors, as $I$ demonstrates. More generally, a matrix is diagonalizable exactly when its characteristic polynomial splits over the chosen field and every eigenvalue has equal geometric multiplicity and algebraic multiplicity. The proof outline is to join bases of the distinct eigenspaces; their direct sum fills the space exactly under these conditions.

A physical motivation is the separation of normal modes. Consider two equal masses $m$ between three identical springs of stiffness $k$, with the outer ends fixed. By Hooke's law and Newton's second law, the displacement vector $q=(q_1,q_2{)}^T$ obeysThe eigenvectors $(1,1{)}^T$ and $(1,-1{)}^T$ have eigenvalues $1$ and $3$: the masses move together in the first normal mode and oppositely in the second. Writing $q=a(t)(1,1{)}^T+b(t)(1,-1{)}^T$ separates the coupled equations into two harmonic oscillators,Their angular frequencies are $\sqrt{k/m}$ and $\sqrt{3k/m}$; the eigenvalues give squared angular frequencies after multiplication by $k/m$. This is the beauty of diagonalization: finding the right directions turns interacting motions into independent patterns. For a physical treatment, see Yen-Jie Lee's "Coupled Oscillators, Normal Modes" (MIT 8.03SC, 2016), and the local article normal modes of two equal masses between three springs.^[ref]

A positive diagonal matrix $D=\mathrm{diag}(d_1,\dots ,d_n)$, with $d_i>0$, is an invertible matrix and changes the coordinate scales through the similarity transformation $B=D^{-1}AD$. Its diagonal entries are still $a_{ii}$, while $b_{ij}=a_{ij}{d}_j/d_i$. Thus the Gershgorin discs have the same centres but different radii. Matrix similarity preserves the characteristic polynomial and eigenvalues, so the original and scaled disk unions are both valid bounds and may be intersected. Suitable scaling can compensate for badly unbalanced off-diagonal entries; it need not shrink every radius.^[ref]

For example,The original Gershgorin discs are $|z-2|\le 100$ and $|z-3|\le 0.01$. Their union is simply the huge first disk; the small second disk contains no eigenvalue. After scaling, both radii are $1$, giving $|z-2|\le 1$ or $|z-3|\le 1$. The two Gershgorin discs overlap, so their individual eigenvalue counts are not certified. The scaled matrix is a real symmetric matrix, however, so matrix similarity now proves that the original matrix has real eigenvalues in $[1,4]$ and is an invertible matrix. Directly, both matrices have characteristic polynomial ${\lambda }^2-5\lambda +5$, henceThe scaling changes the available bounds, while these eigenvalues stay fixed.

Under $B=S^{-1}AS$, an eigenvector in old coordinates becomes $S^{-1}v$ in new coordinates. Indeed,Since $S^{-1}$ is an invertible matrix, the new coordinate vector is nonzero. The inverse conversion $S$ proves that the two eigenspaces have the same dimension, hence the same geometric multiplicity.

For $A=\mathrm{diag}(2,5)$, the eigenvector $e_2=(0,1{)}^T$ has eigenvalue $5$. In the oblique basis of the opening example, its coordinate vector isThe tuple changes from $(0,1)$ to $(-1,1)$, but reconstruction gives $-b_1+b_2=e_2$: the physical vertical direction is unchanged. Calling the eigenvectors unchanged is accurate only for the underlying vectors, not for their coordinate vectors.

Let $A=D+L+L^T$ be a real symmetric positive-definite matrix, with $D$ diagonal and $L$ strictly lower triangular. Put $B=D/\omega +L$ and $C_{\omega }=I-B^{-1}A$ for $\omega \ne 0$. The matrix norm induced by an energy norm reduces the question to $T=A^{1/2}{C}_{\omega }{A}^{-1/2}$. Direct multiplication and $B+B^T-A=(2/\omega -1)D$ giveThe left side is positive semidefinite. The matrix following the scalar coefficient on the right is positive-definite, since $D$ has positive diagonal and $B^{-1}{A}^{1/2}$ is an invertible matrix. For $0<\omega <2$, every eigenvalue of $T^{T}T$ therefore lies in $[0,1)$. Hence its spectral radius is below one and $\Vert C_{\omega }{\Vert }_A=\Vert T{\Vert }_2<1$. Iteration errors consequently decay geometrically in the energy norm. The argument proves convergence from every initial vector, without requiring the original iteration matrix to be symmetric.

An $m\times n$ matrix has full row rank when its matrix rank is $m$, equivalently when its rows are linearly independent vectors. This requires $m\le n$. Its column space is all of ${\mathbb{F}}^m$, so the represented linear map is surjective and every linear system $Ax=b$ is solvable. If $n>m$, its nullity is $n-m>0$, so solutions are not unique.^[ref]

For example, the matrix transpose of the matrix in full column rank isIt has full row rank two. Every output $(p,q{)}^T$ has solutions $(p-t,q-t,t{)}^T$, with $t\in \mathbb{R}$. A square matrix of size $n$ has full row rank and full column rank together exactly when its matrix rank is $n$; then it is an invertible matrix. A nonsquare matrix cannot have both properties, and has no two-sided inverse: such an inverse would make its linear map a linear isomorphism between vector spaces of different dimensions.

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.