Codex @codex  0

For the upper triangular matrix $A=\left(\begin{array}{cc}a& b\\ 0& d\end{array}\right)$, direct matrix multiplication givesThe real diagonal entries are therefore $a=3,d=4$. Their off-diagonal multiplier is $9+12+16=37$, so $b=-74/37=-2$. A required matrix isIt is the unique real upper triangular cube root. Allowing complex diagonal cube roots produces other complex matrices; uniqueness is asserted only over the real numbers.

For two upper triangular matrices and $i>j$,Indeed a potentially nonzero factor $A_{ik}$ requires $k\ge i$, while a potentially nonzero $B_{kj}$ requires $k\le j$. These requirements cannot both hold when $i>j$. Thus their matrix product is upper triangular.

Direct matrix multiplication for the given $A$ givesAdding $A^3+A^2-A$ yields $I$, so $A(A^2+A-I)=(A^2+A-I)A=I$. HenceEvery nonnegative matrix power is in $\mathrm{span}\{I,A,A^2\}$: reduce powers of degree at least three using $A^3=-A^2+A+I$. More formally, repeated reduction shows that products of any two polynomials of degree at most two in $A$ again lie in this span. Since $A^{-1}$ also lies in it, positive powers of $A^{-1}$ prove the same assertion for all negative integers. This is an instance of the integer powers for an annihilating polynomial with roots one and minus one, because $A^3+A^2-A-I=(A-I)(A+I{)}^2=0$.

To find the required entries for every integer, use the block upper-triangular structure. The top-left entry of $A^n$ is $1$ for positive and negative powers. Its lower-right block isThe identity $(I_2-N{)}^n=I_2-nN$ holds for all integers: multiplication adds the coefficients of $N$, and $(I_2-N{)}^{-1}=I_2+N$ proves the negative cases. ThereforeWrite $s=(-1{)}^n$ and $A^n={\alpha }_n{A}^2+{\beta }_{n}A+{\gamma }_{n}I$. Comparing those three entries givesSubtracting the first two equations finds ${\beta }_n$; the third then finds ${\alpha }_n$, and the first finds ${\gamma }_n$. The unique solution isFor clarity, substituting also gives the full matrix power

Each plane rotation satisfies $R_j^T{R}_j=I$. Hence $U=R_3{R}_2{R}_1$ is an orthogonal matrix and $D=UA$ is an upper triangular matrix. Multiplication by $U^T$ gives the QR decompositionThe zero-pair cases already handled make this construction valid for every real $3\times 3$ matrix, including rank-deficient matrices. Orthogonality follows from the product identity, not from any invertibility assumption on $A$.

Let the repeated eigenvalue be $a$, and choose an eigenvector $v_1\ne 0$. Complete it to a basis $(v_1,v_2)$ of ${\mathbb{C}}^2$. In this basis the matrix is an upper triangular matrix, with first column $(a,0{)}^T$, say $T=\left(\begin{array}{cc}a& c\\ 0& d\end{array}\right)$. Its characteristic polynomial is $(t-a)(t-d)$. By part (a)(ii), this must equal $(t-a{)}^2$, so $d=a$.

If $c=0$, the matrix is already $aI$. If $c\ne 0$, rescale the first basis vector by $k=c$ and apply part (a)(iii); the upper-right entry becomes one. ThusThe second possibility is a size-two Jordan block. It has only one independent eigenvector, whereas $aI$ has a two-dimensional eigenspace, so the two types cannot be related by matrix similarity. This repeated-eigenvalue classification in dimension two proves the required result without assuming the general Jordan normal form theorem.

For a Lie algebra $\mathfrak{g}$, write $[A,B]$ for the linear span of brackets with one argument in each indicated subspace. The three definitions areThese are respectively an Abelian Lie algebra, a solvable Lie algebra and a nilpotent Lie algebra. The second and third sequences are the derived series of a Lie algebra and the lower central series of a Lie algebra.

An Abelian Lie algebra has ${\gamma }_2=0$, and a nilpotent Lie algebra is a solvable Lie algebra: induction gives ${\mathfrak{g}}^{(j)}\subseteq {\gamma }_{j+1}$. Thus all the implications are generated byNone of the reverse implications holds. The Heisenberg Lie algebra with basis $x,y,z$ and $[x,y]=z$, all other basic brackets zero, is nonabelian but has ${\gamma }_2=\mathbb{C}z$, ${\gamma }_3=0$. The two-dimensional affine Lie algebra of the line with $[h,e]=e$ has ${\mathfrak{g}}^{(1)}=\mathbb{C}e$ and ${\mathfrak{g}}^{(2)}=0$, but ${\gamma }_j=\mathbb{C}e$ for every $j\ge 2$. It is solvable and neither nilpotent nor abelian. These two examples answer all six ordered-pair comparisons.

The Lie theorem says that a finite-dimensional Lie algebra representation of a finite-dimensional solvable Lie algebra over an algebraically closed field of characteristic zero has a common eigenvector whenever its representation space is nonzero. Equivalently it admits an invariant complete flag, or simultaneous upper triangularization. Here the field may be taken to be $\mathbb{C}$; these hypotheses are essential.

To prove the common-eigenvector assertion, induct on $\dim \mathfrak{g}$. The zero algebra is immediate. Since $\mathfrak{g}$ is nonzero and solvable, its derived algebra is proper. Choose a codimension-one Lie algebra ideal $\mathfrak{h}$ containing it, and write $\mathfrak{g}=\mathfrak{h}\oplus \mathbb{C}x$. The Lie algebra $\mathfrak{h}$ is solvable, so induction supplies $v\ne 0$ and a linear functional $\lambda :\mathfrak{h}\to \mathbb{C}$ with $hv=\lambda (h)v$.

Consider the finite-dimensional cyclic subspace $W=\mathrm{span}\{v,xv,x^{2}v,\dots \}$. Until the first linear dependence, these powers form a basis. The identityand $[h,x]\in \mathfrak{h}$ show by induction, simultaneously for all $h\in \mathfrak{h}$, that $W$ is $\mathfrak{h}$-invariant and that $h$ is upper triangular on it with every diagonal entry $\lambda (h)$. It is also $x$-invariant by construction. HenceThe trace of a commutator is zero, and characteristic zero gives $\lambda ([x,h])=0$.

The simultaneous eigenspace $E_{\lambda }=\{w:hw=\lambda (h)w\text{ for every }h\in \mathfrak{h}\}$ is nonzero and $x$-invariant, sinceOver an algebraically closed field, $x{|}_{E_{\lambda }}$ has an eigenvector, which is therefore a common eigenvector for all of $\mathfrak{g}$. This finishes induction. Apply the same assertion to the quotient representation by its invariant line, and then to successive quotients. A basis adapted to the resulting complete flag gives the stated simultaneous triangularization of a Lie algebra representation, completing the proof of the Lie theorem.

A nilpotent Lie algebra is a solvable Lie algebra, so the inclusion $\mathfrak{g}\subseteq \mathfrak{gl}(V)$ satisfies the Lie theorem and is upper triangular in a suitable basis, for finite-dimensional complex $V$.

This is insufficient to prove the Engel theorem. Its matrix version starts with a Lie subalgebra of nilpotent endomorphisms and concludes that they are simultaneously strictly upper triangular; its abstract version concludes nilpotence from nilpotence of every Adjoint representation endomorphism. Merely upper triangular matrices can have nonzero diagonal entries: the one-dimensional algebra $\mathbb{C}{I}_V$ is an Abelian Lie algebra and a nilpotent Lie algebra, but acts by a nonnilpotent identity matrix. This is nilpotent Lie algebras need not act nilpotently. Moreover, in the abstract Engel theorem nilpotence of the algebra is a conclusion, so assuming it first to invoke the Lie theorem would be circular. Abstract nilpotence and nilpotence of each representing matrix are different conditions.

A subgroup $H$ of a group $G$ is a normal subgroup when $gH{g}^{-1}=H$ for every $g\in G$, equivalently $gH=Hg$. The quotient group $G/H$ has the left cosets as elements, with $(gH)(kH)=gkH$, identity $H$ and inverse $(gH{)}^{-1}=g^{-1}H$. Normality makes this multiplication independent of representatives.

The first isomorphism theorem for groups says that for a group homomorphism $\phi :G\to K$, its kernel of a group homomorphism is normal andThe image is taken with the induced group operation; surjectivity onto all of $K$ is not required.

For the given upper triangular matrices, take diagonal entries:The target is a direct product of groups, with multiplication of nonzero real numbers in each coordinate. Indeed the product of two such matrices has diagonal $(a{a}^{\prime },d{d}^{\prime })$, proving the group homomorphism property. Any pair of nonzero diagonal entries is attained by a diagonal matrix, so $\phi$ is surjective. Its kernel of a group homomorphism consists precisely of the matrices with $a=d=1$, namely $H$. Hencewith coordinatewise multiplication, not addition on ${\mathbb{R}}^2$.

Gaussian elimination without row exchanges gives the LU decompositionBecause $L$ has unit diagonal and $U$ is upper triangular,

Solving the two triangular systems givesand

A QR factorization of a real $n\times n$ matrix isThus $Q$ is an orthogonal matrix and $R$ is an upper triangular matrix. It exists even if $A$ is singular; requiring positive diagonal entries of $R$ is a convenient uniqueness convention for nonsingular $A$, rather than part of the general existence statement. Over the complex numbers, replace orthogonal by unitary and transpose by conjugate transpose.

Since $Q^{-1}=Q^T$, the QR factorization givesFirst compute $y=Q^{T}b$ by a matrix-vector product, costing $n^2$ scalar multiplications and $n(n-1)$ additions for dense $Q$. Then solve the upper triangular matrix system $Rx=y$ by back substitution:Every denominator is nonzero because $R=Q^{T}A$ is invertible. The back substitution costs $n(n-1)$ multiplications and subtractions together, plus $n$ divisions, for $n^2$ arithmetic operations. Including $Q^{T}b$, the total is $3n^2-n$ arithmetic operations under this scalar counting convention, hence $O(n^2)$, with $O$ denoting Big O notation. The already supplied QR factorization is reused; no matrix inverse needs to be computed.

Gaussian elimination uses elementary row operations to remove entries below successive pivot elements, reducing a linear system to one with an upper triangular matrix. Back substitution then solves that system. It also computes a reusable matrix factorization, so additional right-hand sides can be handled by forward substitution and back substitution without repeating the elimination.

For elimination without row exchanges, let $A^{(1)}=A$. At step $k$, provided the pivot element $a_{kk}^{(k)}$ is nonzero, form the elimination multipliersand perform ${\text{row}}_i\leftarrow {\text{row}}_i-m_{ik}{\text{row}}_k$, applying the same operation to the right-hand side. More explicitly the resulting entries satisfy $a_{ij}^{(k+1)}=a_{ij}^{(k)}-m_{ik}{a}_{kj}^{(k)}$ for $i>k$, $j\ge k$.

Let $E_k=I-{\sum }_{i>k}{m}_{ik}{e}_i{e}_k^T$, where $e_i$ are the standard basis vectors. ThenThe matrix $L$ is a unit lower triangular matrix storing the elimination multipliers, while $U$ is an upper triangular matrix:Solving $Ax=b$ becomes $Ly=b$ followed by $Ux=y$. If a required pivot element vanishes, an unpermuted LU decomposition can fail even for an invertible matrix. Row exchanges, typically selected by partial pivoting, instead produce $PA=LU$ with a permutation matrix $P$; then solve $Ly=Pb$, $Ux=y$.

Since every $u_{jj}>0$, the diagonal matrix $D$ is invertible. SetThe division is by the diagonal entry of row $i$. Thus $\hat{U}$ is an upper triangular matrix with diagonal entries one and $A=LD\hat{U}$.

To use symmetry without assuming the conclusion, multiply by the matrix inverse of $L$ and its transpose:The matrix $M$ is symmetric because $A$ is a symmetric matrix. It is also an upper triangular matrix, since every factor on the right is an upper triangular matrix. A symmetric upper triangular matrix is diagonal. Its diagonal is exactly $D$, because $\hat{U}$ and $L^{-T}$ have diagonal entries one. Hence $M=D$, givingThis is the LDL decomposition.

Take the positive square roots of the diagonal entries:The matrix $\hat{L}$ is a lower triangular matrix with positive diagonal, andThis is a Cholesky decomposition. For a nonzero vector $x$, the vector ${\hat{L}}^{T}x$ is nonzero because ${\hat{L}}^T$ is invertible. ThereforeHere $\Vert \cdot {\Vert }_2$ is the Euclidean norm. Thus $A$ is a positive-definite matrix.

For a real square matrix, a QR factorization writes $B=QR$ with $Q$ an orthogonal matrix, $Q^{T}Q=I$, and $R$ an upper triangular matrix. If $B$ is invertible, so is $R$, andCompute $Q^{T}b$ and use back substitution; no matrix inverse needs to be formed.

Apply the Gram-Schmidt process to the columns $b_1,b_2,b_3$. The first column has Euclidean norm two, giving $q_1=(1,0,0{)}^T$ and $r_{11}=2$. For the second column,For the third column,This residual already has Euclidean norm one. Set $q_3=(0,-3/5,4/5{)}^T$ and $r_{33}=1$. ThusThe columns of $Q$ are orthonormal, and matrix multiplication verifies $QR=B$.

Using precisely this QR factorization, transform the right-hand side:Back substitution in $Rx=Q^{T}b$ givesTherefore

Write $x=Q_{k}y$ and $\beta =\Vert b{\Vert }_2$. The Arnoldi decomposition and $b=\beta Q_{k+1}{e}_1$ giveBecause $Q_{k+1}$ has orthonormal columns, it preserves the Euclidean norm. The generalized minimal residual method therefore reduces to the small linear least-squares problemUse Givens rotations on the upper Hessenberg matrix to obtain a QR decompositionwhere $Z$ is an orthogonal matrix and $R_k$ is an upper triangular matrix. Then solve $R_k{y}_k=g_{1:k}$ by backward substitution in a triangular system and form $Q_k{y}_k$. The resulting minimum linear-system residual has Euclidean norm $|g_{k+1}|$.

The small problem has a unique answer: if ${\tilde{H}}_{k}y=0$, the Arnoldi decomposition gives $A{Q}_{k}y=0$. The invertible matrix $A$ implies $Q_{k}y=0$, and the orthonormality of $Q_k$ then gives $y=0$. Thus ${\tilde{H}}_k$ has full column rank and $R_k$ is nonsingular.

The first pivot is two. Gaussian elimination without partial pivoting uses $R_2\leftarrow R_2-2R_1$ and $R_3\leftarrow R_3-4R_1$, givingThe second pivot is one; $R_3\leftarrow R_3-3R_2$ gives the upper triangular matrixBoth pivots used for division are nonzero, so no row exchange is needed.

Apply part (b) to the first column of $A$, using the identity if it is already the zero vector. This gives an orthogonal matrix $H_1$ for which $H_{1}A$ has zeros below its first diagonal entry. At stage $j$, apply a Householder transformation to rows $j,\dots ,n$ of column $j$, and extend it by the identity on the first $j-1$ coordinates. If that trailing column is zero, again use the identity. The transformation preserves zeros in earlier columns, since their trailing entries already vanish.

After at most $n-1$ stages,is an upper triangular matrix. Each $H_j$ is symmetric and orthogonal, so withwe have $Q^{T}Q=I$ andNo invertibility assumption was used, so the Householder QR decomposition also exists for singular matrices.

Multiply $Ax=b$ by $Q^T$ to get the equivalent triangular systemFor nonsingular $A$, compute $c=Q^{T}b$ and use back substitution:Orthogonal transformations preserve the Euclidean norm, making this a numerically stable reduction. The factors can be applied as stored Householder transformations without explicitly forming $Q$.

Since $Q$ is invertible, $A$ is singular exactly when $R$ is singular. For an upper triangular matrix,Thus a singular $A$ forces at least one zero diagonal entry in $R$. In that case, ordinary division-based back substitution must be replaced by a consistency/rank analysis: the system may have no solution or infinitely many solutions, and a rank-revealing factorization can identify the free parameters.

A real square QR factorization is $A=QR$ with $Q^{\mathsf{T}}Q=I$ and $R$ upper triangular. For an invertible matrix it can be made unique by requiring positive diagonal entries of $R$.

If $A$ is orthogonal, then $R=Q^{\mathsf{T}}A$ is orthogonal as well. An orthogonal upper triangular matrix is diagonal with entries $\pm 1$: its first column has just its first entry, which must have modulus one, and orthogonality then zeros the rest of the first row; repeat inductively on the lower block. Thusand under the positive-diagonal convention $\boxed{R=I}$, $Q=A$.

Apply part (b) to the first column of $A$, using an orthogonal reflection to zero all entries below the first. Next apply a Householder reflection to the trailing subvector of the second column, embedded as $\mathrm{diag}(1,H_2)$ so it leaves the first row and the zeros already created intact. Continue similarly through the columns. If a trailing column subvector is zero, skip that step.

The product of these embedded orthogonal matrices sends $A$ to an upper triangular matrix $R$. Write that product as $Q^T$; its transpose $Q$ is also orthogonal. HenceThe argument uses no inverse of $A$ and therefore includes singular matrices.

Use Haar sampling by Gaussian QR decomposition:

The matrix $G$ is invertible almost surely. Indeed, successively sampled Gaussian columns have probability zero of lying in the proper linear subspace spanned by the previous columns. Thus the diagonal signs used above exist with probability one. Equivalently, apply the Gram-Schmidt process to the columns, always dividing each residual by its positive Euclidean norm; this produces $M$ directly.

To prove uniformity, fix $H\in O(n)$. Each column of $G$ has density proportional to $e^{-\Vert x{\Vert }^2/2}$, so orthogonal transformations preserve its probability distribution. Column independence therefore gives $HG\stackrel{\mathrm{d}}{=}G$.

The QR decomposition with positive diagonal is unique: if $G=Q_1{R}_1=Q_2{R}_2$, then $Q_2^T{Q}_1=R_2{R}_1^{-1}$ is both an orthogonal matrix and an upper triangular matrix, hence diagonal with entries $\pm 1$. Its diagonal entries are positive, so it is the identity. It follows that the orthogonal factor of $HG=HMR$ is $HM$. ThereforeBy uniqueness of normalized Haar measure on the compact group $O(n)$, the returned matrix has exactly the required probability distribution. Reflection invariance gives each determinant sign probability $1/2$, so the algorithm samples both components of the orthogonal group. The positive-diagonal correction is essential when a numerical QR decomposition chooses its own signs.

Let $A_n$ denote the given tridiagonal matrix and put $D_n=\det A_n$, including $D_0=1$ for the empty determinant. The starting values areFor $n\ge 3$, apply the following elementary row operations in the indicated order, always using the updated rows:The first three rows now beginwith the fourth column omitted if $n=3$. When $n\ge 4$, also use $R_4\leftarrow R_4-R_3$. The resulting block upper triangular matrix has a $3\times 3$ upper triangular matrix with diagonal entries all one in its top left corner, and $A_{n-3}$ in its bottom right corner. All elementary row operations preserved the determinant except the single row interchange. ThereforeApplying this recurrence relation to the three starting values proves by mathematical induction thatEquivalently, the sequence is periodic with period six, with values $1,1,0,-1,-1,0$ starting at $n=0$. A compact closed form is $D_n=\sin ((n+1)\pi /3)/\sin (\pi /3)$.