Codex @codex  0

For either an upper triangular matrix or a lower triangular matrix,In the permutation formula for the determinant, every contribution except the diagonal product includes an entry on the zero side of the diagonal. Equivalently, successive cofactor expansions along the first column of an upper triangular matrix prove the formula by mathematical induction.

Perform the elementary row operations from the bottom upwards:This order matters because each subtraction uses the predecessor's original row. For example,The other two differences are $(0,0,1-t^2,t-t^3)$ and $(0,1-t^2,t-t^3,t^2-t^4)$. Thus the required upper triangular matrix isThese elementary row operations use no division, so the reduction remains valid for all real numbers $t$, including $t=\pm 1$.

The elementary row operations preserve the determinant, and the diagonal product of the upper triangular matrix found above isConsequentlyAt $t=1$, all four rows are equal. At $t=-1$, successive rows alternate between one row and its negative. In either case the matrix rank is one, confirming the vanishing determinant.

Apply the elementary row operations from bottom to top: $R_4\leftarrow R_4-R_3$, $R_3\leftarrow R_3-R_2$, and $R_2\leftarrow R_2-R_1$. This order ensures that each subtraction uses the original preceding row. The result is the upper triangular matrixPut ${\delta }_1=a$, ${\delta }_2=b-a$, ${\delta }_3=c-b$, ${\delta }_4=d-c$. Row $i$ is either zero if ${\delta }_i=0$, or has its first nonzero entry in column $i$. Thus, for arbitrary real parameters, a row echelon form is obtained by retaining the nonzero rows of $T$ in their existing order and moving every zero row to the bottom. This deals explicitly with vanishing parameters; an upper triangular matrix with an intermediate zero row is not yet a row echelon form.

The subtractions preserve the determinant, so the original matrix hasA square matrix is invertible exactly when its determinant is nonzero. Consequently,These conditions concern consecutive parameters: no ordering, positivity, or pairwise distinctness of all four is required. More generally the rank of a matrix here is the number of nonzero ${\delta }_i$, because the retained nonzero rows have distinct leading columns.

Let $U,V$ be $n\times n$ upper triangular matrices. For an entry below the diagonal, $i>j$, matrix multiplication givesIf $k<i$, then $U_{ik}=0$. If $k\ge i$, then $k>j$, so $V_{kj}=0$. Every summand is zero, givingThus $UV$ is an upper triangular matrix. Equivalently, a potentially nonzero summand would require $i\le k\le j$, impossible below the diagonal.

Suppose an invertible matrix has two LU factorizations, $A=L_1{U}_1=L_2{U}_2$, with $L_1,L_2$ unit lower triangular matrices and $U_1,U_2$ upper triangular matrices. All four factors are invertible matrices, since their square products are invertible. Multiplication by the appropriate inverse matrices givesBy the supplied closure properties, the left side is a unit lower triangular matrix and the right side is an upper triangular matrix. A matrix of both types is diagonal; its diagonal entries are all one. Thus both sides are the identity matrix, whenceQualification of the printed wording: this establishes uniqueness if the specified LU factorization exists. Invertibility alone does not guarantee an unpivoted LU factorization. For example $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ is invertible, but in a product $\left(\begin{array}{cc}1& 0\\ \ell & 1\end{array}\right)\left(\begin{array}{cc}{u}_{11}& u_{12}\\ 0& u_{22}\end{array}\right)$, the zero top-left entry forces $u_{11}=0$, making the bottom-left entry $\ell u_{11}=0$ as well, contrary to the required value one. A permutation matrix is needed in general, as in PLU factorization.

The elementary row operations used above add multiples of other rows, so preserve the determinant. The determinant of an upper triangular matrix is the product of its diagonal entries. HenceEquivalently, $\det L=1$ and multiplicativity of the determinant gives $\det A=\det L\det U=6$.

The determinant of the unit lower triangular matrix $L$ is 1. There is one row swap, so $\det P=-1$, and the upper triangular matrix has determinant $1\cdot (-2)\cdot (3/2)\cdot 2=-6$. Therefore

Substitute the QR decomposition into the normal equations:The diagonal of $R$ is nonzero, so $R^T$ is invertible. Cancel it algebraically to obtainCompute the three inner products in $Q^{T}b$, then use back substitution in this upper triangular matrix. There is no need to form an inverse or explicitly construct $A^{T}A$. The orthogonal projection of $b$ onto the column space is $Q{Q}^{T}b$; its orthogonal residual proves that this solution minimizes $\Vert Ay-b{\Vert }_2$.

If $B$ is an invertible upper triangular matrix, $B^T$ is invertible and lower triangular. Part (ii) makes $(B^T{)}^{-1}$ lower triangular, while part (i) identifies it with $(B^{-1}{)}^T$. Transposing gives that $B^{-1}$ is upper triangular. This deduction uses both the inverse-transpose identity and the lower-triangular result.

Apply Gaussian elimination to the supplied nonsymmetric matrix,The first pivot element is $-2$, with elimination multiplier $l_{21}=2/(-2)=-1$. Perform $R_2\leftarrow R_2+R_1$, givingThe second pivot element is $-1$, with elimination multiplier $l_{32}=-1$. Perform $R_3\leftarrow R_3+R_2$, then use the third pivot element $-2$ and elimination multiplier $l_{43}=-1$ to perform $R_4\leftarrow R_4+R_3$. The LU factorization isHere $L$ is a unit lower triangular matrix, hence an invertible matrix, and $U$ is an upper triangular matrix. No row interchange is needed: all three pivot elements used in elimination are nonzero. The final diagonal entry is zero, with an entirely zero last row; there is no further division by it. The three nonzero rows of $U$ are linearly independent, so the matrix rank is $3$ and $A$ is a singular matrix. Direct matrix multiplication gives $LU=A$.

Choose a fixed time increment $h=\Delta t>0$, let $t_n=nh$, and approximate $\mathbf{c}(t_n)$ by ${\mathbf{c}}_n$. The Backward Euler method evaluates the transport term at the new time:Rearrange to the linear systemAlthough $A$ is a singular matrix, $B$ is an invertible matrix for every $h>0$. In each row, its diagonal entry is $1+2h$ and the sum of the absolute values of its off-diagonal entries is $2h$; hence it is a strictly diagonally dominant matrix. Its Gershgorin discs have centre $1+2h$ and radius $2h$, excluding zero. In particular, the zero eigenvalue of $A$ becomes an eigenvalue $1$ of $B$.

The algorithm uses Reusing LU factors for multiple right-hand sides:

Both triangular solves use the factors of $I-hA$. The LU factorization of the singular transport matrix $A$ from part (a) is not a solver for this new linear system. No matrix inverse needs to be formed. Since $A$ and $h$ are fixed, the same LU factorization serves every step; only the right-hand side changes. A varying $\mathbf{b}(t)$ would give $r_n={\mathbf{c}}_n-h\mathbf{b}(t_{n+1})$ without changing these factors.

As a check, multiplying the update by $1^T$ givesexactly reproducing the inventory balance at the sampled times, apart from roundoff error. The Backward Euler method has temporal global error $O(h)$ for smooth solutions, so its A-stability does not remove the need to select $h$ for accuracy.

A matrix factorization incorporating a permutation matrix, a unit lower triangular matrix and an upper triangular matrix. The convention $A=PLU$ differs from $PA=LU$ by replacing $P$ with its inverse. When pivoting during elimination, previously stored lower-triangular multipliers must be permuted consistently with the rows.

A reduced QR decomposition of an $m\times k$ matrix over the real numbers with full column rank, $m\ge k$, writes $A=QR$, where $Q$ is $m\times k$ with orthonormal columns and $R$ is a $k\times k$ upper triangular matrix with positive diagonal. Applying the Gram-Schmidt process to the columns $v_j$ of $A$ constructs $Q=(q_1\cdots q_k)$ and records the coefficientsThis last column identity is exactly the matrix multiplication $A=QR$. The upper triangular matrix records that the $j$th input uses only the first $j$ new directions, while its positive diagonal records the norms of the nonzero orthogonal projection residuals. Since $Q^{T}Q=I$, one also has $R=Q^{T}A$; $Q^T$ denotes the transpose and $I$ the identity matrix. Over the complex numbers, use the conjugate transpose $Q^{\ast }$ in these identities.

For the three-dimensional Gram-Schmidt process example, the exact matrices areFor example, the last column reconstructs asThe diagonal entries are approximately $1.414214,1.224745,1.154701$. Each is a norm of the new direction before it was scaled to length one.

For a linear least-squares problem, the orthogonal projection of $b$ onto the column space of $A$ is $Q{Q}^{T}b$. Hence the minimizing coefficients solve the linear system $Rx=Q^{T}b$ by back substitution. Let $A_2=(v_1{v}_2)$ consist of the first two columns of the example; its reduced factors are $Q_2=(q_1{q}_2)$ and the leading $2\times 2$ block $R_2$ of $R$. For $b=(0,0,1{)}^T$, the linear system $R_{2}x=Q_2^{T}b$ isThus $A_{2}x=(1/3,-1/3,2/3{)}^T$, agreeing with the orthogonal projection computed above, and the minimum Euclidean norm of $A_{2}x-b$ is $1/\sqrt{3}$. The QR decomposition separates building an orthonormal basis from recovering coefficients in the original basis.^[ref]

Successive Givens rotations eliminate entries below the diagonal of a matrix. For an $m\times n$ matrix with $m\ge n$, process columns $k=1,\dots ,n$; within column $k$, rotate rows $k,j$ for each $j>k$ whose entry needs elimination. Apply each Givens row-pair update to columns $k,\dots ,n$. Both rows are zero in earlier columns, so these operations preserve earlier eliminations. No assumption of full column rank is needed to perform the eliminations.

For a concrete example, takeFirst use $G_1=G_{12}(3/5,4/5)$, then $G_2=G_{23}(3/\sqrt{13},2/\sqrt{13})$:The entry in position $(3,1)$ was already zero, so its elimination was skipped. The second Givens rotation combines the remaining pair $(3,2{)}^T$ in column two. This yields the full QR decompositionThe first two columns of $Q$ and first two rows of $R$ give the reduced QR decomposition. Direct multiplication verifies both $QR=A$ and $Q^{T}Q=I$. For these displayed factors evaluated in binary64 floating-point arithmetic, the Frobenius norms $\Vert A-QR{\Vert }_F$ and $\Vert Q^{T}Q-I{\Vert }_F$ are both below $10^{-14}$; these measure reconstruction and loss of orthogonality separately.

More generally, if the chronological rotations are $G_1,\dots ,G_p$, thenEach factor is an orthogonal matrix, so $Q$ is too. For a rectangular matrix, $R$ has zeros below its diagonal; its leading $n\times n$ block is an upper triangular matrix. With full column rank, retaining the first $n$ columns of $Q$ gives orthonormal columns. To impose a positive diagonal when necessary, flip matching columns of $Q$ and rows of $R$, preserving their product.

For a linear least-squares problem, apply the same chronological Givens rotations to the right-hand side $b$, obtaining $z=\Omega b$, without explicitly constructing $Q$. Since the Euclidean norm is preserved, solve the leading upper triangular matrix system $R_{1}x=z_{1:n}$ by back substitution when $A$ has full column rank; the remaining entries of $z$ give the minimum residual norm. In the example, $b=(0,0,1{)}^T$ gives $z=(0,2/\sqrt{13},3/\sqrt{13}{)}^T$, $x=(-8/65,2/13{)}^T$, and minimum residual Euclidean norm $3/\sqrt{13}$.

The locality is useful for a sparse matrix or an existing QR decomposition needing an extra row: only two rows change at each step, and the new row can be eliminated against the stored upper triangular matrix. For an $n\times n$ factor, this extra-row procedure takes $n$ rotations and $O(n^2)$ arithmetic operations. Locality does not guarantee preservation of sparsity: mixing rows can create nonzeros wherever either row had one. For a fully populated $m\times n$ input, the straightforward elimination uses ${\sum }_{k=1}^n(m-k)$ rotations, each touching $n-k+1$ columns, giving $O(m{n}^2)$ work. Storage layout, zero patterns and implementation affect speed; this count alone establishes no universal advantage over other QR decomposition algorithms.

The Euclidean norm preservation explains the appeal for numerical stability: exact rotations do not amplify a perturbation's length. Rounded coefficients and Givens row-pair updates still introduce roundoff error. Small reconstruction and orthogonality residuals check the computed factors, while the condition number of the original problem still controls how accurately a linear least-squares problem determines its solution.

A square matrix is strictly upper triangular if every entry on or below its diagonal is zero. A product of $n$ such $n$-by-$n$ matrices vanishes, so they form a nilpotent Lie algebra under the commutator. Multiplication by an upper triangular matrix preserves strict upper triangularity and zero trace.

A linear map on a finite-dimensional vector space over an algebraically closed field has both an upper triangular matrix and a lower triangular matrix in suitable bases. One proof uses invariant subspaces and annihilators to make the induction step entirely in the dual space.

Choose an eigenvector $v$ and let $U=\mathrm{span}\{v\}$. The dual map preserves the annihilator of a vector subspace $U^0$, of dimension one less. By induction, choose a basis of $U^0$ making the restriction upper triangular. Extend this to a basis of the whole dual space; its matrix $C$ remains upper triangular because $U^0$ is an invariant subspace. In the corresponding primal basis, the matrix is $C^T$, which is lower triangular. Reversing the primal basis makes it upper triangular. Dimension zero and one start the induction. This also allows the original eigenvector to be the first vector of the resulting upper triangular basis.

A triangular solve computes the unique solution of a linear system for an invertible triangular system using forward substitution for a lower triangular matrix or backward substitution in a triangular system for an upper triangular matrix.

The unitriangular group ${\mathrm{UT}}_n(F)$ consists of upper triangular matrices over a field $F$ with every diagonal entry equal to one. Every such matrix is $I_n+N$ for a strictly upper triangular matrix $N$. Products have the same form, and $N^n=0$ gives the inverseThus these matrices form a subgroup of the general linear group. The case ${\mathrm{UT}}_3({\mathbb{F}}_3)$ is noncommutative but every element has cube equal to the identity matrix: $(I_3+N{)}^3=I_3$ because $N^3=0$ and $3=0$ in the finite field ${\mathbb{F}}_3$.