Eigenvalue Decomposition
Non-invertibility can arise when training instances do not span the entire space of R^d.
When Directions Are Missing
In least squares, it is tempting to solve A w = b by multiplying both sides by the inverse of A. That plan fails when A is non-invertible because a non-invertible matrix does not have an inverse. One important cause of non-invertibility is that the training instances occupy only part of the space R^d. They do not span every direction, so the matrix does not have full coverage of the directions needed to behave invertibly.
Non-invertible does not mean useless. It means that direct inversion is unavailable. A solution can still exist when b is in the range of A.
Following the Available Directions
The key change in viewpoint is to stop trying to invert A directly. Because A is symmetric, it can be represented using an eigenvalue decomposition. This representation separates the matrix into orthonormal eigenvector directions and the diagonal values associated with those directions. Each diagonal value tells us how the matrix handles its corresponding direction.
Symbolic Decomposition of a Non-Invertible System
Training instances generate only part of R^d, A is non-invertible, and b lies in the range of A. Explain the solution procedure without using a direct inverse.
Identify the limitation: The training instances do not span the whole space, so A does not cover every direction in the way required for invertibility.
Decompose A: Represent A as V D Vᵀ. The columns of V provide orthonormal eigenvector directions, while D records the associated diagonal values.
Inspect D: Separate the diagonal positions whose values are zero from those whose values are nonzero.
Construct D+: Put zero in D+ wherever D has a zero diagonal entry. Put the reciprocal of each nonzero diagonal entry in the matching position of D+.
Interpret the result: Use the eigenvector directions rather than a direct inverse of A. Since b is in the range of A, the relevant projection gives b itself.
The lack of an inverse does not prevent a solution in this case. Eigenvalue decomposition handles the usable directions through reciprocals and gives special treatment to the zero directions.
The Zero-and-Reciprocal Rule
The diagonal matrix D+ processes D one diagonal position at a time. If the diagonal entry Dii is zero, the corresponding entry of D+ is also zero. If Dii is nonzero, the corresponding entry of D+ is its reciprocal. Thus D+ does not pretend that a zero direction can be inverted. It preserves the zero while applying reciprocals only where reciprocation is defined.
| Entry in D | Entry in D+ | Meaning |
|---|---|---|
| Zero | Zero | The corresponding direction is not inverted |
| Nonzero | Its reciprocal | The corresponding direction is handled through reciprocation |
The diagonal rule for constructing D+
Projection onto the Relevant Span
The decomposition also gives a geometric interpretation. Instead of requiring b to be represented through every direction in R^d, the method works with the span of the relevant eigenvector columns. In the situation described here, that span agrees with the span of the training instances, and b already belongs to it. Therefore the projection of b onto that span is b itself.
When b is already in the span of the training instances, and that span agrees with the relevant eigenvector span, the projection does not shorten or alter b. It returns b itself.
Null Directions and Solution Ambiguity
The eigenvector directions associated with zero diagonal entries are the directions that the decomposition cannot recover through reciprocation. They represent the missing coverage revealed by non-invertibility. Consequently, reasoning about a solution must focus on the directions represented by the matrix rather than assuming that every direction in R^d can be independently recovered.
| Reasoning claim | Assessment | Correct interpretation |
|---|---|---|
| A is non-invertible, so no solution exists | Incorrect | A solution can exist when b is in the range of A |
| Multiply by A inverse | Unavailable | A has no inverse when it is non-invertible |
| Use eigenvalue decomposition | Appropriate | Work with eigenvector directions and diagonal entries |
| Project onto the relevant span | Appropriate | Represent the component of b supported by the eigenvector span |
Reasoning Errors to Avoid
Assuming that every non-invertible matrix makes A w = b unsolvable.
The absence of an inverse concerns the matrix operation, not automatically the existence of a solution for every particular b.
Fix:
Check whether b belongs to the range of A. In the source situation, it does, so a solution is possible.Trying to multiply both sides by A's inverse.
A non-invertible matrix does not have an inverse.
Fix:
Use the eigenvalue decomposition and handle the diagonal entries through D+.Taking the reciprocal of every diagonal entry of D.
The zero direction cannot be handled by reciprocation.
Fix:
Put zero in the matching position of D+ when the corresponding entry of D is zero.Treating the eigenvector span as if it had to cover every direction in R^d.
The projection interpretation works with the span represented by the matrix and the training instances.
Fix:
Interpret Âw as the projection of b onto the relevant eigenvector span.
Practice the Decomposition
Suppose training instances span only part of R^d. The resulting matrix A is non-invertible, b lies in the range of A, and A is represented as V D Vᵀ. Describe what you do with a zero diagonal entry of D, what you do with a nonzero diagonal entry, and why the final result can still represent b.
Hints
- Start with the zero-versus-nonzero rule for D+.
- Then connect the eigenvector columns of V to the relevant span.
- Finally use the fact that b lies in the range of A.
What do you think happens?
If A is non-invertible but b lies in the range of A, must the equation A w = b have no solution?
Reveal answer
Answer: No, because b can lie in the range of A.
The absence of an inverse does not prevent a solution when b is in the range of A.
What to Remember
- Training instances that fail to span all of R^d can leave a matrix without the full directional coverage needed for invertibility.
- A non-invertible matrix has no inverse, but A w = b can still have a solution when b lies in the range of A.
- Eigenvalue decomposition rewrites the problem in orthonormal eigenvector directions and diagonal values.
- D+ assigns zero to zero diagonal entries and reciprocals to nonzero diagonal entries.
- The resulting interpretation is a projection of b onto the span of the relevant eigenvector directions; when b already lies in that span, the projection gives b itself.
Key Takeaways
- Missing training-instance directions can make A non-invertible.
- Non-invertibility removes the direct-inverse method but does not automatically remove all solutions.
- Eigenvalue decomposition separates directional behavior into eigenvectors and diagonal entries.
- D+ keeps zero entries zero and replaces nonzero entries with reciprocals.
- Âw can be understood as the projection of b onto the span represented by the relevant eigenvector directions.