An orthonormal basis makes coordinates and projections easy, but a given basis seldom arrives orthonormal. Gram–Schmidt constructs one without changing the successive subspaces generated by the input list. Its essential step is a residual: remove what earlier directions already explain, then normalize what remains. A zero residual signals dependence, not a direction that can be normalized.
The existing inner-products lesson establishes Gram–Schmidt; spaces and maps supplies the vector-space foundations. This section develops prefix spans, dependent lists and thin QR.
Notation and conventions
Let be a finite-dimensional real or complex inner-product space. We use an inner product linear in the first argument. In orthonormal column coordinates,
Thus the coefficient of a unit vector in a vector is , not . The star is conjugate transpose; over the reals it is ordinary transpose.
Definition 9.1.1
(Residual against an orthonormal list)
Let be an orthonormal list in and let . The residual of against the list is
For the empty list the sum is empty and . The ordered prefix spans of a list are the subspaces for .
Remove previous directions
Suppose first that are linearly independent. Define recursively as the residual of against , and .
Theorem 9.1.2
(Gram–Schmidt for independent input)
Let be linearly independent. Put
Then every , so the recursion is defined; the list is orthonormal; and
Proof
(Orthogonality, nonzero residuals and equal prefix spans)
Argue by induction on , assuming are orthonormal with the stated prefix spans. For each ,
The residual is therefore perpendicular to all previously retained directions. It cannot be zero: otherwise the defining equation would put in their span, which by induction is the span of its input predecessors, contrary to independence. Normalization is consequently legitimate and gives a new unit vector perpendicular to the others.
The reconstruction equation is
It shows , so the prefix span of the 's lies in that of the 's. Conversely every residual is a combination of and earlier , hence of , so lies in the prefix span of the 's. Both inclusions hold.
Proof X-ray
Where independence enters, and why both inclusions are needed
The proof uses independence exactly once: to make , which is what allows division. Orthogonality does not need it, because the cancellation works for any residual. The induction hypothesis is used twice: orthonormality of the earlier makes the sum collapse to a single term, and equality of the earlier prefix spans turns "" into " is a combination of ".
Orthogonality alone would not prove equal spans: orthonormal vectors could lie in a different -dimensional subspace. The inclusion that the reconstruction equation gives, together with a dimension count or the direct inclusion in the other direction, closes the argument. Without independence, the same computation would still show orthogonality at each nonzero step, but at a zero residual the recursion stops.
The result depends on the input order. The final span is fixed, but a different order usually produces different intermediate directions. Multiplying an input by a complex phase can also change its normalized direction. What is fixed is the stated recursive construction with positive real residual norms.
Common mistake
(Putting the arguments of the coefficient in the wrong order)
With an inner product linear in the first argument, the coefficient of in is . Take and in . The correct coefficient is , giving residual , which is perpendicular to . The reversed coefficient gives , whose inner product with is . Over the reals the two orders agree, so the error appears only over .
Dependent lists require omission
For a general ordered list, maintain the orthonormal list retained so far. Subtract the projection onto that list from the next input. If the residual is nonzero, append its normalization. If it is zero, omit that input and retain the current list unchanged.
At every stage, the retained span equals the input prefix span. A zero residual is equivalent to the current vector belonging to the earlier retained span, so omission loses no information. A nonzero residual increases the span dimension by one. Induction proves that the final retained list is an orthonormal basis of the whole input span, even when the original list contains zero vectors or repeated vectors.
This is an exact-arithmetic statement. In floating-point calculations a tiny residual is not automatically an exact dependence certificate. A numerical threshold requires a separate error analysis; no such numerical claim is made here.
Counterexample mode
Gram–Schmidt on a dependent list
Claim: running the independent-input recursion on any vectors returns orthonormal vectors. Take and in . Then , and , so the projection is and . The formula would divide by : there is no second unit vector, and the span is a line, so no orthonormal list of length can lie in it. Repair: omit an input whose residual is zero, and report the number of retained vectors, here .
Worked example 9.1.3
(A dependent list with a repeated direction)
Take , , in . First . For : , so the projection is and the residual is ; omit . For : , the projection is and , with , so . The retained list has two vectors, equal to the rank of the input list. Check: , and .
The triangular reconstruction is thin QR
Let be a real or complex matrix with linearly independent columns, so . Apply the construction to its columns, put , and set
Theorem 9.1.4
(Thin QR factorization)
If is an matrix with linearly independent columns, then with and upper triangular with positive real diagonal. This factorization is unique.
Proof
(Existence from the reconstruction, uniqueness by forced steps)
Existence is the reconstruction equation read column by column, together with orthonormality of the .
For uniqueness let be any such factorization. Its first column forces ; norm one and a positive diagonal force and determine . Inductively, suppose are determined. Taking the inner product of with for fixes . The remaining part is , so its positive norm fixes and then .
Here has only the needed orthonormal columns. When , is the projection onto the column space, not the identity on the ambient space. Without the positive-diagonal convention, signs or complex phases can move between the two factors.
For dependent columns the retained has columns and the reconstruction matrix has size . It is not a square invertible triangular matrix. One must not infer that a full-column-rank QR factorization exists after merely omitting zero residuals without changing these dimensions.
Worked example 9.1.5
(Thin QR of a matrix)
Let with columns , . Then and . Next , and , with . So and . Check and reconstruct the second column: . Since , : for instance sends to .
A Gram matrix checks the calculation
For a full-column-rank factorization,
The determinant identity follows by multiplying the determinants of the two square triangular factors; the diagonal entries are positive real numbers even in the complex case. More generally a Gram matrix has entries in row , column . It is positive definite exactly when the vectors are independent, because its quadratic value at a coefficient column is the squared norm of the corresponding linear combination.
This supplies a useful independent check on residual lengths. For the worked example, has determinant , and . It does not replace checking orthonormality: a correct determinant alone cannot establish every inner product.
Concept lensAlgebraic
The triangular factor as a Cholesky factor
Since with upper triangular with positive diagonal, is the Cholesky factor of the Gram matrix , and for a positive definite matrix this factor is unique under the positive-diagonal convention. Gram–Schmidt on the columns of therefore produces the same triangular matrix as factorizing the Gram matrix alone, without forming . In the example, with .
The same construction works for polynomials
Vectors need not be coordinate columns. On real polynomials of bounded degree, define
It is an inner product. Symmetry and bilinearity follow from the integral. If a nonzero polynomial had zero squared norm, continuity and a point in the interval where it is nonzero would instead give a small interval on which its square is bounded below by a positive number, a contradiction. Such a point exists because a nonzero polynomial cannot vanish on an interval.
Applying Gram–Schmidt to monomials therefore produces orthonormal polynomials. Their coefficients are obtained by actual inner-product integrals, not by treating their monomial coordinate columns as Euclidean vectors.
Worked example 9.1.6
(Orthonormalizing on )
, so . For : (odd integrand), so , and . For : , giving projection on , and . Thus with , so . Check: .
Checklist and common errors
- For independent input, every residual is nonzero, and every prefix span is preserved.
- For dependent input, omit zero residuals and report the dimension of the retained basis. Do not divide by zero.
- With the first-linear convention the coefficient is ; conjugation is essential over the complex field.
- Thin QR for independent columns has and an upper triangular with positive real diagonal. These requirements give uniqueness.
- In a non-Euclidean inner product, use its actual pairings to compute coefficients and norms.
For a proposed answer, check the pairings, the residual norms and reconstruction. Orthogonal vectors need not be unit vectors; an orthonormal list need not span the desired space; and a correctly shaped matrix product is not sufficient unless it reproduces the input.
Quick checks
Quick check
(Apply one Gram–Schmidt step to and in : find and the residual .)
Solution · Answer
. , so the projection is and . It is perpendicular to : .
Quick check
(The list in is fed to Gram–Schmidt with omission. How many vectors are retained, and which input is omitted?)
Solution · Answer
Two are retained. , , and the residual of against them is , so the third input is omitted. The count equals .
Quick check
(If is a thin QR factorization of an matrix and , is ?)
Solution · Answer
No. has rank , so it cannot be the identity. It is the orthogonal projection onto the column space of ; only holds.