Codex @codex  0

For a complex $n\times n$ matrix $A$, $\mathrm{tr}(A^k)$ is the sum of the $k$th powers of its eigenvalues, counted with algebraic multiplicity. This does not require diagonalizability: a similar upper triangular matrix has the eigenvalues on its diagonal, and taking powers raises those diagonal entries to their corresponding powers. Newton's identities therefore recover its characteristic polynomial from the first $n$ such traces.

For the Jordan block $A=\left(\begin{array}{cc}2& 1\\ 0& 2\end{array}\right)$, $\mathrm{tr}A=4$ and $\mathrm{tr}(A^2)=8$. Hence $e_1=4$ and $e_2=(4^2-8)/2=4$, giving $\det (zI-A)=z^2-4z+4=(z-2{)}^2$. The repeated eigenvalue is recovered even though this matrix is not diagonalizable.^[ref]

For a finite-dimensional complex representation $V$ with character ${\chi }_V$, the exterior square has characterIf the eigenvalues of $g$ on $V$ are ${\lambda }_1,\dots ,{\lambda }_d$, counted with algebraic multiplicity, its eigenvalues on the exterior square are ${\lambda }_i{\lambda }_j$ for $i<j$. Expanding the square of their sum giveswhich proves the formula by taking traces. A basis giving an upper triangular matrix suffices for this argument, so diagonalizability is unnecessary.

At the identity, the formula becomes $\dim {\bigwedge }^{2}V=(d^2-d)/2=\left(\genfrac{}{}{0ex}{}{d}{2}\right)$. This supplies a quick consistency check before using the character to decompose the representation.

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.

Forward substitution solves a linear system $Ly=c$ with a lower triangular matrix $L$ and nonzero diagonal, from the first row downward:The first sum is empty, so $y_1=c_1/l_{11}$. Each subsequent row uses only components already found. For a unit triangular matrix $L$, omit the division because $l_{ii}=1$. The complementary procedure, back substitution, solves an upper triangular matrix system from the last row upward.^[ref]

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.

A Givens rotation eliminates one component of a vector by rotating just two coordinates, preserving its Euclidean norm. For example,The length remains five: elimination moves the component into the retained coordinate rather than discarding it. Applied to a matrix, the same operation mixes two rows; QR decomposition by Givens rotations uses these local operations to build an upper triangular matrix.

For indices $i<j$, the matrix $G_{ij}(c,s)$ is the identity matrix except for its block on coordinates $i,j$:This article uses left matrix multiplication on column vectors. If $c=\cos \theta$ and $s=\sin \theta$, the block is a rotation matrix through angle $-\theta$: the minus sign belongs in the lower left. Its transpose reverses the rotation. Direct multiplication gives $G^{T}G=I$ and determinant one, so it is an orthogonal matrix; consequently $\Vert Gx{\Vert }_2^2=x^T{G}^{T}Gx=\Vert x{\Vert }_2^2$. Only two coordinates change, but this Euclidean norm identity holds for the entire vector.

Generate a real $n$-by-$n$ matrix $G$ with independent entries having the standard normal distribution. Take its QR decomposition with positive diagonal in the upper triangular matrix factor, $G=QR$. The orthogonal matrix $Q$ has normalized Haar measure on the full orthogonal group $O(n)$. If a numerical factorization returns $Q_0{R}_0$, set $S=\mathrm{diag}(\mathrm{sgn}{R}_{0,ii})$ and return $Q_{0}S$. The signs are nonzero almost surely: successively drawn Gaussian columns have probability zero of lying in the proper linear subspace spanned by earlier columns.

For correctness, every fixed orthogonal matrix $U$ preserves the standard Gaussian column density and column independence, so $UG$ and $G$ have the same probability distribution. The positive-diagonal QR decomposition is unique: two decompositions would give an orthogonal matrix that is also an upper triangular matrix with positive diagonal, hence the identity. Therefore $Q(UG)=UQ(G)$ and $Q(G)$ has a left-invariant probability law. Uniqueness of normalized Haar measure on the compact group $O(n)$ identifies that law. Each determinant sign has probability $1/2$ by reflection invariance.

A Householder QR decomposition introduces zeros below successive diagonal entries using orthogonal reflections. For a nonzero real column segment $x$, set $\sigma =1$ when $x_1\ge 0$ and $\sigma =-1$ otherwise, and defineThen $H^{T}H=I$ and $Hx=-\sigma \Vert x{\Vert }_2{e}_1$. The sign choice avoids subtracting nearly equal numbers when constructing $v$. If the segment is zero, skip the reflection.

For $A\in {\mathbb{R}}^{m\times n}$ with $m\ge n$, apply the first reflection to all rows, the second to rows $2,\dots ,m$, and so on, extending each by an identity on the earlier rows. This giveswhere $Q$ is orthogonal and $R$ consists of an $n\times n$ upper triangular matrix above $m-n$ zero rows. The reflections are stored through their defining vectors, so a full dense $Q$ need not be formed.^[ref]

For full column rank, the top $n\times n$ block of $R$ is invertible and back substitution solves the transformed least squares problem. Orthogonal transformations preserve the Euclidean norm, making this route useful when the normal equations would square a large condition number.

Apply the preceding Householder reflection to the columns ofThe first column becomes $(-5,0{)}^T$ and the second becomes $(-11/5,2/5{)}^T$:Thus an orthogonal matrix multiplying an upper triangular matrix reconstructs $A$. The zero below the diagonal came from a geometric operation that preserves Euclidean norms and inner products.

Our positive-diagonal convention for QR decomposition is obtained by a sign adjustment. With $D=\mathrm{diag}(-1,1)$, putThen $Q^{T}Q=I$ and $\boxed{A=Q{R}_{+}}$. The intermediate sign chooses an orientation for a basis vector; the adjustment makes the diagonal positive.

For a larger matrix, the next Householder reflection acts only on the lower rows of the remaining columns, retaining the zeros already created. Store its defining vector and apply $z\mapsto z-2u(u^{T}z)$ instead of forming a dense reflection matrix. This links a simple mirror operation to efficient QR decomposition, including least-squares solutions.

An LU decomposition writes a square matrix as $A=LU$, with $L$ a lower triangular matrix and $U$ an upper triangular matrix. We use a unit triangular matrix $L$, meaning $l_{ii}=1$. The factors record Gaussian elimination: $U$ contains the reduced equations, while $L$ stores the elimination multipliers needed to reconstruct the original equations. This makes Reusing LU factors for multiple right-hand sides inexpensive.^[ref]

For an invertible matrix, unpivoted LU decomposition requires nonzero pivot elements at every elimination step; invertibility alone does not guarantee this. In general use Pivoted LU decomposition, with the explicit convention $PA=LU$ and a permutation matrix $P$. Once the factors exist, solving a linear system $Ax=b$ needs forward substitution followed by back substitution, rather than forming a matrix inverse.

When Gaussian elimination without row interchanges is defined, an upper Hessenberg matrix needs at most one elimination per pivot column, because only its first subdiagonal can be nonzero. The LU decomposition has a unit lower bidiagonal matrix $L$ and an upper triangular matrix $U$. If the input matrix is also symmetric, it is a tridiagonal matrix and $U$ is upper bidiagonal.

The nonzero-pivot condition is essential: $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ is upper Hessenberg and invertible but has no such unpivoted LU decomposition. A pivoted factorization can still be computed, with its permutations recorded explicitly.

A matrix decomposition expresses a matrix as a matrix product of factors with simpler structure. An LU decomposition uses triangular factors, a QR decomposition uses an orthogonal matrix and a triangular factor, and a singular value decomposition separates input directions, stretching factors and output directions. The factorization is an identity; the chosen structure determines what it helps compute.

For an original two-by-two example,The outer factors are a lower triangular matrix and an upper triangular matrix, each with unit diagonal as in a unit triangular matrix; the middle factor is a diagonal matrix. Their matrix product is $M$, and the final diagonal entry $5/2$ is the Schur complement of the first entry $2$. This is the scalar version of the factorization under block elimination.

To solve $Mz=(3,4{)}^T$, solve with the three factors in their displayed order from left to right: first the lower triangular factor, then the diagonal factor, then the upper triangular factor. The intermediate vectors are $(3,5/2{)}^T$ and $(3/2,1{)}^T$, giving the concise answer $z=(1,1{)}^T$. A new right-hand side uses the same factors. This is why Reusing LU factors for multiple right-hand sides is useful: factorization records work that otherwise would be repeated, while forward substitution and back substitution apply it cheaply.^[ref]

Different decompositions reveal different features. A Cholesky decomposition uses positive definiteness of a symmetric matrix, while a singular value decomposition also applies to rectangular matrices and exposes matrix rank. The existence and numerical behaviour of the factors depend on their own hypotheses; for example, an unpivoted LU decomposition can fail when a chosen pivot element is zero even though the matrix is an invertible matrix.

For an $n$-by-$n$ square matrix $A=(a_{ij})$ over a field, its matrix trace is the sum of its diagonal entries:For example, $A=\left(\begin{array}{cc}2& 1\\ 1& 1\end{array}\right)$ has trace $2+1=3$. Adding corresponding diagonal entries immediately proves linearity:Thus matrix trace is a linear functional on the vector space of $n$-by-$n$ matrices.^[ref]

The surprising point is that the sum is intrinsic to a linear operator, even though individual diagonal entries depend on the basis. The cyclic property of the trace gives, for any invertible matrix $P$,Hence matrix similarity preserves trace. For the example above, choose the change-of-basis matrix $P=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$. ThenThe diagonal entries have changed but their sum has not. This makes trace useful for extracting a feature of the underlying linear operator without finding a preferred basis.

Over the complex numbers, or over the real numbers after allowing complex eigenvalues, the trace equals their sum with algebraic multiplicity:No diagonalizable matrix hypothesis is needed.^[ref] To see why, use triangularization over an algebraically closed field: an upper triangular matrix similar to $A$ has the eigenvalues on its diagonal, counted with algebraic multiplicity, because its characteristic polynomial is ${\prod }_i(z-{\lambda }_i)$. Similarity preserves trace, so summing that diagonal proves the formula.

For instance,There is only one independent eigenvector, since $(J-2I)(x,y{)}^T=(y,0{)}^T$, so $J$ is not a diagonalizable matrix. Nevertheless its repeated eigenvalue contributes twice. For our earlier $A$, the characteristic polynomial is $z^2-3z+1$, its eigenvalues are $(3+\sqrt{5})/2$ and $(3-\sqrt{5})/2$, and their sum is $3$. An inexpensive diagonal sum therefore gives spectral information before solving the characteristic polynomial.

The trace of a real matrix does not give that linear map's volume factor: that factor is the absolute value of its determinant. For example, $2I_2$ has trace $4$ and area factor $4$, but $2I_3$ has trace $6$ and volume factor $8$. Their occasional numerical agreement in two dimensions is a coincidence. The connection between trace and local volume change gives a geometric interpretation near the identity matrix, and describes the volume rate of a flow map generated by a linear system of differential equations.

For a matrix $v$ supported in its first row and any upper triangular matrix $a$, multiplication gives $av=a_{11}v$. Thus $Av=Kv$ has dimension at most one for every $v$, whereas the entire module has dimension three. Hence this module is not cyclic, over every field $K$.

The Cayley-Hamilton theorem statesLet $d=\dim V$. Extend the field to an algebraically closed field and choose a basis in which the matrix of $T$ is an upper triangular matrix, as permitted. Write its diagonal entries as ${\lambda }_1,\dots ,{\lambda }_d$ and put $V_i=\mathrm{span}(e_1,\dots ,e_i)$. Each $V_i$ is an invariant subspace, andApply $T-{\lambda }_{d}I$ first, then $T-{\lambda }_{d-1}I$, and continue. The resulting product sends $V_d$ into $V_0=\{0\}$. These factors are commuting operators, soThe determinant of an upper triangular matrix gives ${\chi }_T(x)=(-1{)}^d{\prod }_i(x-{\lambda }_i)$. Thus ${\chi }_T(T)=0$ after the field extension. Its entries were in the original field, whose embedding is injective, so they were already zero there. The zero-dimensional case is immediate as well.

In the monomial basis $\mathcal{B}=(1,x,x^2,x^3)$ of the complex vector space $V=\mathbb{C}[x{]}_{\le 3}$, the binomial theorem givesThe characteristic polynomial of this upper triangular matrix is the product of $t$ minus its diagonal entries, so ${\chi }_T(t)=(t-1{)}^4$.

For the minimal polynomial, set $\Delta =T-I$, the forward difference with step one. For a nonconstant polynomial of polynomial degree $d$, the binomial theorem shows that $f(x+1)-f(x)$ has polynomial degree $d-1$. Constant polynomials have zero forward difference. Consequently ${\Delta }^4=0$ on $V$. To prove that the nilpotency index is exactly four, computeIt follows thatIf $T$ were diagonalizable, its only eigenvalue would be $1$, and its diagonal matrix in an eigenbasis would be $I$. This would make $T=I$, whereas $T(x)=x+1\ne x$. Thus $T$ is not diagonalizable. Equivalently, its minimal polynomial has a repeated root.

We prove by mathematical induction on $n=\dim V$ that every linear map on an $n$-dimensional complex vector space admits both triangular forms. For $n=0$ or $1$ this is immediate. When $n>1$, the fundamental theorem of algebra supplies an eigenvector $v$; its span $U=⟨v⟩$ is an invariant subspace.

By parts (ii) and (iii), $U^0$ has dimension $n-1$ and is an invariant subspace of the dual map $T^{\prime }$. Apply the induction hypothesis to $T^{\prime }{|}_{U^0}$ to choose a basis ${\phi }_1,\dots ,{\phi }_{n-1}$ with an upper triangular matrix. Extend it by a linear functional ${\phi }_n$ satisfying ${\phi }_n(v)=1$. Such a functional exists by basis extension, and cannot belong to $U^0$. In this basis of $V^{\prime }$, the matrix of $T^{\prime }$ has the formwhere $B$ is an upper triangular matrix; here the last diagonal entry follows by evaluating $T^{\prime }{\phi }_n$ at $v$, where $Tv=\lambda v$.

There is a basis $e_1,\dots ,e_n$ of $V$ with ${\phi }_i(e_j)={\delta }_{ij}$, since the dual basis construction gives a finite-dimensional bidual evaluation map isomorphism. In particular $e_n=v$. The matrix transpose relationship for a dual map givesa lower triangular matrix. Reversing this basis turns a lower triangular matrix into an upper triangular matrix. If $R$ is the permutation matrix reversing the order, we have provedThis completes the induction by triangularization using dual spaces.

Use the Leibniz formula for determinants:For a nonzero product in an upper triangular matrix, every selected column must satisfy $\sigma (j)\ge j$. But a permutation has ${\sum }_j\sigma (j)={\sum }_{j}j$, so every one of these inequalities is an equality. Only the identity permutation can contribute. Its sign is positive and its product is ${\prod }_j{m}_{jj}$, which proves the result even if some diagonal entries vanish.

In the matrix product, $(AB{)}_{ij}={\sum }_{k=1}^n{a}_{ik}{b}_{kj}$. A nonzero summand in a product of upper triangular matrices requires both $i\le k$ and $k\le j$. If $i>j$, no such index exists, so the product is upper triangular. If $i=j$, only $k=i$ survives, givingThis also shows inductively why the diagonal of an integer matrix power consists of the corresponding powers of the diagonal entries.