Eigenvalue Decomposition

The decomposition also gives a geometric interpretation.

Programming

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.

How can training instances occupy only a lower-dimensional subspace, and how does that missing span make the matrix non-invertible?

Key point

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.

How do the eigenvector directions and eigenvalues transform the system A w = b into directions that can be handled or discarded?

Worked example

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.

1
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.
2
Decompose A
Represent A as V D Vᵀ. The columns of V provide orthonormal eigenvector directions, while D records the associated diagonal values.
3
Inspect D
Separate the diagonal positions whose values are zero from those whose values are nonzero.
4
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+.
5
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.

Result

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.

What happens to each coordinate when D+ keeps the reciprocal of a nonzero eigenvalue but assigns zero to a zero eigenvalue?

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.

How does Âw represent the component of b that lies within the span of eigenvector directions?

Key point

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.

Which eigenvector directions are lost when their eigenvalues are zero, and how does D+ distinguish them from usable directions?

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

Common distinctions when solving a non-invertible system

Reasoning Errors to Avoid

Common mistake
Assuming that every non-invertible matrix makes A w = b unsolvable.
What it looks like
A is non-invertible, but b lies in the range of A.
Why it fails
The absence of an inverse concerns the matrix operation, not automatically the existence of a solution for every particular b.
Do this instead
Check whether b belongs to the range of A. In the source situation, it does, so a solution is possible.
Common mistake
Trying to multiply both sides by A's inverse.
What it looks like
Writing w = A inverse times b even though A is non-invertible.
Why it fails
A non-invertible matrix does not have an inverse.
Do this instead
Use the eigenvalue decomposition and handle the diagonal entries through D+.
Common mistake
Taking the reciprocal of every diagonal entry of D.
What it looks like
Applying reciprocation to a zero diagonal entry.
Why it fails
The zero direction cannot be handled by reciprocation.
Do this instead
Put zero in the matching position of D+ when the corresponding entry of D is zero.
Common mistake
Treating the eigenvector span as if it had to cover every direction in R^{^d}.
What it looks like
Expecting the method to reconstruct components of b outside the span generated by the relevant eigenvector columns.
Why it fails
The projection interpretation works with the span represented by the matrix and the training instances.
Do this instead
Interpret Âw as the projection of b onto the relevant eigenvector span.

Practice the Decomposition

MEDIUM

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.

Your attempt (not saved)

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?

Yes, because non-invertibility always prevents a solution
No, because b can lie in the range of A
Only if every diagonal entry of D is nonzero

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

1
Training instances that fail to span all of R^{^d} can leave a matrix without the full directional coverage needed for invertibility.
2
A non-invertible matrix has no inverse, but A w = b can still have a solution when b lies in the range of A.
3
Eigenvalue decomposition rewrites the problem in orthonormal eigenvector directions and diagonal values.
4
D+ assigns zero to zero diagonal entries and reciprocals to nonzero diagonal entries.
5
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.

At a glance

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.

Related concepts

More concepts starting with E