Write and let . The stated Euclidean norm gives
Taking nonnegative square roots proves . At this is equality. This is a contraction bound in the transformed coordinates; an arbitrary nonorthogonal does not give the same unit-constant bound for the original error norm.
For the spectral error bound for a diagonalizable fixed-point iteration, the exact solution is a fixed point: . Subtracting it from the iteration gives the error recurrence , with . Multiplying by and using gives
Iterating proves , including because . This argument does not assume is orthogonal; it simply expresses the error in an eigenbasis.
From zero, the first update is . For the next update, the first component is , the second is , and the third is . Therefore .
Update the unknowns in row order, immediately using newly computed components. The component equations are
Thus and . Using only old values in all three row equations would instead describe the Jacobi method, not the Gauss-Seidel method.
The image of a linear map of is exactly the one-dimensional span of : its formula always returns a multiple of , and . Hence .
The rank-nullity theorem gives . Since by (e)(i), . This includes the case , where the complementary projector is zero.
For a sum of mutually orthogonal projectors, orthonormality gives for and one for . Therefore equals zero for different indices and for equal indices. Expanding the finite sum yields
Thus every stated partial sum is a projector. Its image of a linear map is the span of the first orthonormal set of vectors; arbitrary sums of idempotent matrices would not have this conclusion.
Prove both inclusions. If belongs to the column space of , then for some and . Thus .
Conversely, if , then , which explicitly writes as an image of a linear map under . Hence . The two inclusions prove . No orthogonality assumption was used.
A triangular matrix has determinant equal to the product of its diagonal entries, so and . A permutation matrix exchanging two rows has determinant . Using multiplicativity of the determinant in yields . Hence .
Apply the same permutation to the right-hand side and solve two triangular systems. Forward substitution in gives
so . Back substitution in gives , , and . Therefore . Substitution in the original system returns , as required.
Eliminate the first column using multipliers and . The two residual rows have second entries zero and four, so interchange their order for the next pivot. One resulting Pivoted LU decomposition is
The factors below the first pivot must follow the permuted row order, which is why contains before . Direct multiplication gives rows , and in both and . This checks the permutation convention rather than confusing with a different placement of .
For the specified row and column, expand the two matrix products and reorder only finite sums:
The middle equality uses scalar associativity and distributivity, and the interchange of two finite sums. Together with their equal dimensions, equality of every entry proves .
The product is , so multiplying it by the matrix gives an matrix. The product is , so multiplying it on the left by the matrix also gives an matrix. Both multiplications have matching inner dimensions.
Suppose a vector lies outside the span of . Then is linearly independent: in an equation , a nonzero would express in that span, and with the independence of forces every .
This would give linearly independent vectors in a space with an -vector basis, contrary to the supplied claim. Therefore spans . Independence plus spanning makes a basis.
For the equal-cardinality basis criterion, because spans , repeatedly remove a vector whenever it is a linear combination of the others. Such a removal does not change the span. The finite process ends with a linearly independent spanning subset , hence a basis of .
If the original were linearly dependent, at least one removal would occur and . But a basis of an -dimensional vector space has vectors. Equivalently, apply the allowed claim to the basis and any fixed -vector basis of : the latter would wrongly be linearly dependent. Thus no removal was possible. The original spanning set is linearly independent and therefore a basis.
The supplied factors give . Back substitution in yields and , so
Multiplying by the original matrix gives , so this least-squares minimizer has residual zero: this particular overdetermined system is exactly consistent. Full column rank still guarantees uniqueness of the minimizer.
Substitution gives . Since is invertible, cancel it on the left to obtain the nonsingular triangular system
This is the reduced QR least-squares solution. Its geometric justification is the orthogonal decomposition
The second term is independent of , while invertibility of lets the first term be zero at exactly one point. Although , one must not replace by : is tall and its product is the orthogonal projection onto its column space.
From the zero initial vector, the linear-system residual is . Then , , and . The step is , giving
As a check, the new residual is , orthogonal to the preceding residual as expected after this exact line search. It is nonzero, so one iteration has not already solved the system.
Real symmetry and positive definiteness are sufficient, and the preceding parts establish both properties for this matrix. If a residual becomes zero, stop: the solution has been reached and the displayed step quotient should not be evaluated as .
For a convergence justification, let solve , let , and let . The quadratic energy error is . Moving by , with , is exact line search for a positive-definite quadratic and gives
Writing for the extreme eigenvalues, one has and . Therefore
The factor lies below one, so the energy tends to zero and positive definiteness forces . Here the bound is , since the eigenvalues are 1 and 11. This proves convergence for every initial vector, rather than merely checking one numerical iteration.

There are unlisted articles, also show them or only show them.