Existence of Eigenvalues and Eigenvectors

Q: Why does this proof avoid determinants, and does that matter?

The determinant route is perfectly valid but heavier: it needs the determinant to be defined, needs $\det(A - xI_n)$ to be a polynomial of degree $n$, and needs the singularity criterion. The argument here uses only linear dependence and polynomial factorisation. Isolating those two ingredients shows precisely what the theorem rests on and makes it transportable to settings, such as operators on abstract vector spaces, where no determinant is available.

Q: Why does the theorem fail over the real numbers?

The factorisation step is the only place where the field matters, and over $\mathbb{R}$ a polynomial need not factor into linear pieces — $z^{2}+1$ does not. Concretely, the quarter-turn rotation of the plane has the annihilating polynomial $z^{2}+1$, with no real roots, and geometrically it leaves no real direction invariant. Over $\mathbb{C}$ its eigenvalues are $i$ and $-i$.

Q: Does the construction find all the eigenvalues?

No. It produces exactly one, determined by the starting vector and the ordering of the linear factors. If the starting vector happens to lie in a small invariant subspace, the annihilating polynomial can have degree well below $n$ and its roots will be only part of the spectrum. Establishing an upper bound of $n$ on the number of distinct eigenvalues is a separate result.

Q: Why must the vector $\vec{z}$ be non-zero?

Because $k$ was chosen as the smallest index at which the accumulated product of factors annihilates $\vec{x}$. The vector $\vec{z}$ is what the first $k-1$ factors produce, and if it were zero then $k-1$ would already have that property, contradicting minimality. When $k = 1$ no factors have been applied and $\vec{z} = \vec{x}$, which is non-zero by hypothesis.

Q: Is the annihilating polynomial unique?

No. Any non-trivial dependence relation among the Krylov vectors gives one, and any multiple of an annihilating polynomial is also annihilating. There is a unique monic annihilating polynomial of least degree for a given vector — the minimal polynomial of that vector — and every other annihilating polynomial for it is a multiple of that one.

Q: How is this related to Krylov subspace methods?

Directly. The sequence $\vec{x}, A\vec{x}, \ldots, A^{n}\vec{x}$ is the Krylov sequence, and the forced dependence at step $n+1$ is what bounds the dimension of the Krylov subspace. Arnoldi and Lanczos build the same subspace but orthonormalise the basis as they go, and they extract eigenvalue estimates from a small projected matrix instead of from polynomial coefficients — keeping the mathematics and discarding the numerical defects.

Q: Should I ever compute an eigenvalue this way?

Only for demonstration on a small matrix with exact arithmetic. The power basis loses conditioning within a few steps, and finding the roots of a degree-$n$ polynomial from its coefficients is ill-conditioned even when the eigenvalues themselves are well separated. Production eigenvalue computation uses Hessenberg reduction with shifted QR for dense matrices and restarted Arnoldi or Lanczos for sparse ones.

Overview

The definition of an eigenpair asserts nothing about existence. It says what it means for a scalar and a non-zero vector to satisfy $A\vec{x} = \lambda\vec{x}$ , but leaves open whether any square matrix actually has such a pair. That gap must be closed before eigenvalue methods can be relied on, and closing it is not a formality: over the real numbers the statement is simply false, since a planar rotation leaves no real direction invariant.

Over the complex numbers the answer is affirmative and unconditional. Every square matrix has at least one eigenvalue, and with it at least one eigenvector. The usual route to this result runs through the determinant: the characteristic polynomial $\det(A - xI_n)$ has a root by the fundamental theorem of algebra, and that root is an eigenvalue. The argument given here avoids determinants entirely, which is worth doing because it isolates exactly what the result depends on — a counting fact about linear dependence and the factorisation of complex polynomials — and because it generalises to settings where no determinant is available.

The mechanism is a sequence. Take any non-zero starting vector and repeatedly apply the matrix, producing $\vec{x}, A\vec{x}, A^{2}\vec{x}, \ldots, A^{n}\vec{x}$ . That is $n+1$ vectors living in an $n$ -dimensional space, so they must be linearly dependent. The coefficients of a dependence relation are the coefficients of a polynomial that annihilates the matrix at that vector. Factoring the polynomial over $\mathbb{C}$ into linear pieces and applying those pieces one at a time to the starting vector must eventually reach zero, and the last factor applied before that happens hands over an eigenvalue and a non-zero eigenvector together.

The proof is constructive in the strict sense: follow its steps and an eigenpair falls out. It is nonetheless a poor algorithm, requiring the roots of a degree- $n$ polynomial and a badly conditioned basis of matrix powers. Its practical importance is indirect but substantial — the sequence it builds is the Krylov sequence, and the modern iterative eigenvalue and linear solvers are all refinements of exactly this construction with the numerical defects engineered out.

Definition

Every Square Matrix Has an Eigenvalue

ESMHE

Let $A$ be a square matrix of size $n$ with entries in $\mathbb{C}$ . Then $A$ has at least one eigenvalue: there exist $\lambda \in \mathbb{C}$ and $\vec{x} \in \mathbb{C}^n$ with $\vec{x} \ne \vec{0}$ such that $A\vec{x} = \lambda\vec{x}$ .

The hypothesis that scalars are drawn from $\mathbb{C}$ is indispensable. Over $\mathbb{R}$ the statement is false: the quarter-turn rotation $\begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}$ has no real eigenvalue, because it maps no real direction onto a multiple of itself.

Krylov Sequence of a Matrix and a Vector

For a square matrix $A$ of size $n$ and a non-zero $\vec{x} \in \mathbb{C}^n$ , the sequence $\vec{x},\ A\vec{x},\ A^{2}\vec{x},\ \ldots,\ A^{n}\vec{x}$ . It contains $n+1$ vectors in an $n$ -dimensional space and is therefore linearly dependent, whatever $A$ and $\vec{x}$ may be. The span of an initial segment is a Krylov subspace.

Annihilating Polynomial of a Vector

APV

A non-zero polynomial $p$ with $p(A)\vec{x} = \vec{0}$ for a specified non-zero $\vec{x}$ . Any linear dependence among the Krylov sequence supplies one. The monic annihilating polynomial of least degree is the minimal polynomial of $\vec{x}$ with respect to $A$ , and its roots are all eigenvalues of $A$ .

Concepts

Step one: the counting argument

Choose any non-zero $\vec{x} \in \mathbb{C}^n$ — the choice is entirely free, and only the zero vector is excluded. Form the $n+1$ vectors $\vec{x}, A\vec{x}, A^{2}\vec{x}, \ldots, A^{n}\vec{x}$ . A set of more than $n$ vectors in $\mathbb{C}^n$ is always linearly dependent, so there are scalars $a_0, a_1, \ldots, a_n$ , not all zero, with $a_0\vec{x} + a_1A\vec{x} + \cdots + a_nA^{n}\vec{x} = \vec{0}$ . No property of $A$ is used at this stage beyond its being square: the dependence is forced by dimension alone.

Step two: the relation has genuine degree

The relation could conceivably be trivial in a way that defeats the argument, namely if $a_0$ were the only non-zero coefficient. That case is impossible: it would give $a_0\vec{x} = \vec{0}$ with $a_0 \ne 0$ and $\vec{x} \ne \vec{0}$ , and a non-zero scalar multiple of a non-zero vector is never zero. So some $a_i$ with $i \ge 1$ is non-zero. Let $m$ be the largest index with $a_m \ne 0$ ; then $m \ge 1$ . Dividing the whole relation by $a_m$ makes the polynomial monic without changing anything, since scaling a dependence relation preserves it.

Step three: factoring over the complex numbers

Define $p(z) = a_0 + a_1z + \cdots + a_mz^{m}$ with $a_m = 1$ and $m \ge 1$ . Collecting the dependence relation using distributivity gives $p(A)\vec{x} = \vec{0}$ . Because the coefficients lie in $\mathbb{C}$ , the fundamental theorem of algebra factors $p$ completely into linear pieces: $p(z) = (z - b_m)(z - b_{m-1})\cdots(z - b_1)$ for complex numbers $b_1, \ldots, b_m$ , not necessarily distinct. Substituting the matrix gives $\left(A - b_mI_n\right)\cdots\left(A - b_1I_n\right)\vec{x} = \vec{0}$ . This is the only step at which $\mathbb{C}$ rather than $\mathbb{R}$ is essential, and it is exactly where the real-case counterexample fails.

Step four: peel the factors until the vector dies

Apply the factors one at a time, starting with $A - b_1I_n$ , and watch the running product. The full product is the zero vector, so at some point the result becomes zero for the first time. Let $k$ be the smallest index for which $\left(A - b_kI_n\right)\cdots\left(A - b_1I_n\right)\vec{x} = \vec{0}$ ; necessarily $k \le m$ . Define $\vec{z} = \left(A - b_{k-1}I_n\right)\cdots\left(A - b_1I_n\right)\vec{x}$ , understood as $\vec{z} = \vec{x}$ when $k = 1$ . By the minimality of $k$ , the vector $\vec{z}$ is not zero — that is precisely what minimality asserts.

Step five: read off the eigenpair

By construction $\left(A - b_kI_n\right)\vec{z} = \vec{0}$ . Expanding, $A\vec{z} - b_kI_n\vec{z} = \vec{0}$ , hence $A\vec{z} = b_k\vec{z}$ . Since $\vec{z} \ne \vec{0}$ , the definition of an eigenpair is satisfied exactly: $\vec{z}$ is an eigenvector of $A$ with eigenvalue $b_k$ . The theorem is proved, and no determinant has appeared anywhere in the argument.

What the proof does and does not deliver

It delivers one eigenvalue, not all of them, and which one depends on both the starting vector and the order in which the linear factors are applied. Reordering the factors of the same polynomial generally produces a different eigenvalue. It gives no information about multiplicity, no bound on the number of eigenvalues, and no guarantee that the polynomial produced is the characteristic polynomial — an unlucky starting vector can yield a polynomial of degree well below $n$ whose roots are only some of the eigenvalues. Establishing that a matrix of size $n$ has at most $n$ distinct eigenvalues is a separate result.

The construction, step by step

Choose any non-zero $\vec{x}$ The starting vector is arbitrary. Only

\vec{x} = \vec{0}

is forbidden, because it makes every subsequent vector zero.

Build the Krylov sequenceForm

\vec{x}, A\vec{x}, \ldots, A^{n}\vec{x}

by repeated matrix-vector products. These

n+1

vectors in

\mathbb{C}^n

must be dependent.

Find a dependence relationSolve the homogeneous system whose columns are the Krylov vectors. Any non-trivial solution gives the coefficients

a_0, \ldots, a_n

Form and factor the polynomialTake

m

as the highest index with

a_m \ne 0

, normalise

a_m = 1

, and factor

p(z)

into linear factors over

\mathbb{C}

Apply factors until zero appearsMultiply

\vec{x}

A - b_1I_n

, then

A - b_2I_n

, and so on. Stop at the first factor that produces the zero vector.

Report the eigenpairThe vector immediately before the collapse is the eigenvector; the root belonging to the factor that caused the collapse is the eigenvalue.

Equations

The Krylov sequence and its forced dependence

EQ-EEE-01

S = {\vec{x}, A \vec{x}, A^{2} \vec{x}, \dots, A^{n} \vec{x}}, | S | = n + 1 > n = \dim (ℂ^{n})

More vectors than the dimension of the space, so the set is linearly dependent regardless of $A$ and of the choice of $\vec{x}$ .

A non-trivial relation of linear dependence

EQ-EEE-02

A non-trivial relation of linear dependence

The coefficients come from any non-trivial solution of the homogeneous system whose columns are the Krylov vectors.

The annihilating polynomial

EQ-EEE-03

p (z) = a_{0} + a_{1} z + \dots + a_{m} z^{m}, a_{m} = 1, m \geq 1 \Rightarrow p (A) \vec{x} = \vec{0}

Collecting the dependence relation using distributivity. The index $m$ is the largest with $a_m \ne 0$ , and $m \ge 1$ because $a_0\vec{x} = \vec{0}$ alone is impossible.

Factored form over the complex numbers

EQ-EEE-04

p (z) = (z - b_{m}) \dots (z - b_{1}) \Rightarrow (A - b_{m} I_{n}) \dots (A - b_{1} I_{n}) \vec{x} = \vec{0}

The fundamental theorem of algebra supplies the complete factorisation. This step, and only this step, requires the scalars to be complex.

The first index at which the product vanishes

EQ-EEE-05

k = min {j : (A - b_{j} I_{n}) \dots (A - b_{1} I_{n}) \vec{x} = \vec{0}}, 1 \leq k \leq m

The set is non-empty because $j = m$ belongs to it. Minimality is what guarantees the vector produced at the previous stage is non-zero.

The eigenvector

EQ-EEE-06

\vec{z} = (A - b_{k - 1} I_{n}) \dots (A - b_{1} I_{n}) \vec{x} \neq \vec{0}, \vec{z} = \vec{x} when k = 1

The last non-zero vector in the peeling process. Its non-vanishing is exactly the statement that $k$ was chosen minimal.

The eigenpair produced

EQ-EEE-07

(A - b_{k} I_{n}) \vec{z} = \vec{0} \Rightarrow A \vec{z} = b_{k} \vec{z}, \vec{z} \neq \vec{0}

The definition of an eigenpair, satisfied with eigenvalue $b_k$ and eigenvector $\vec{z}$ . The theorem is complete.

Variable Definitions

Symbols used on this page
Symbol	Name	Meaning	Domain / type
$A$	Matrix	The square matrix shown to possess an eigenvalue	n x n matrix over C
$n$	Size	Common row and column count of $A$ ; the Krylov sequence has $n+1$ members	positive integer
$\vec{x}$	Starting vector	Any non-zero vector chosen to seed the Krylov sequence	non-zero vector in C^n
$a_{i}$	Dependence coefficient	Scalars in a non-trivial relation of linear dependence on the Krylov sequence	complex scalars, not all zero
$m$	Polynomial degree	Largest index with $a_m \ne 0$ ; the degree of the annihilating polynomial, at least $1$	integer from 1 to n
$b_{i}$	Root	A root of the annihilating polynomial, giving the linear factor $A - b_iI_n$	complex scalar
$k$	Collapse index	The first stage at which the accumulated product of factors sends $\vec{x}$ to zero	integer from 1 to m
$\vec{z}$	Eigenvector produced	The last non-zero vector before the collapse; the eigenvector for $b_k$	non-zero vector in C^n
$I_{n}$	Identity matrix	Used to form the shifted factors $A - b_iI_n$	n x n matrix

Worked Numerical Example

Problem statement

A third-order discrete-time filter has the companion state matrix below. Follow the existence construction literally — Krylov sequence, dependence relation, factorisation, peeling — to produce an eigenpair from scratch, and then show that reordering the factors delivers a different eigenvalue.

State the matrix and choose a starting vector
Any non-zero vector will serve. The first standard basis vector is chosen because it makes the early Krylov products trivial to compute.
$A = [\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 2 & - 5 & 4 \end{matrix}], \vec{x} = [\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}]$
Build the Krylov sequence
Apply $A$ repeatedly, each product using the previous result. Four vectors in $\mathbb{C}^3$ are guaranteed to be linearly dependent, so the sequence stops at $A^{3}\vec{x}$ .
$\vec{x} = [\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}], A \vec{x} = [\begin{matrix} 0 \\ 0 \\ 2 \end{matrix}], A^{2} \vec{x} = [\begin{matrix} 0 \\ 2 \\ 8 \end{matrix}], A^{3} \vec{x} = [\begin{matrix} 2 \\ 8 \\ 22 \end{matrix}]$
Find a dependence relation
Solve the homogeneous system with the four Krylov vectors as columns. The second entry gives $2a_2 + 8a_3 = 0$ , so $a_2 = -4a_3$ ; the third gives $2a_1 + 8a_2 + 22a_3 = 0$ , so $a_1 = 5a_3$ ; the first gives $a_0 + 2a_3 = 0$ , so $a_0 = -2a_3$ . Taking $a_3 = 1$ fixes the relation.
$- 2 \vec{x} + 5 A \vec{x} - 4 A^{2} \vec{x} + A^{3} \vec{x} = \vec{0}$
Verify the relation and form the polynomial
Check entry by entry: $-2(1,0,0) + 5(0,0,2) - 4(0,2,8) + (2,8,22)$ gives $(-2+2,\ -8+8,\ 10-32+22) = (0,0,0)$ . The highest non-zero coefficient is $a_3 = 1$ , so $m = 3$ and the polynomial is already monic.
$p (z) = z^{3} - 4 z^{2} + 5 z - 2, p (A) \vec{x} = \vec{0}$
Factor over the complex numbers
The polynomial factors with a repeated root. Both roots are real in this instance, but the argument would proceed identically with complex roots — that is the point of insisting on $\mathbb{C}$ .
$p (z) = (z - 1)^{2} (z - 2), b_{1} = 1, b_{2} = 1, b_{3} = 2$
Peel the factors one at a time
Apply $A - I_3$ , then $A - I_3$ again, then $A - 2I_3$ , keeping the running vector at each stage. The first two products are non-zero; the third collapses.
$(A - I_{3}) \vec{x} = [\begin{matrix} - 1 \\ 0 \\ 2 \end{matrix}], (A - I_{3}) [\begin{matrix} - 1 \\ 0 \\ 2 \end{matrix}] = [\begin{matrix} 1 \\ 2 \\ 4 \end{matrix}], (A - 2 I_{3}) [\begin{matrix} 1 \\ 2 \\ 4 \end{matrix}] = [\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}]$
Identify the eigenpair and verify it
The collapse occurred at $k = 3$ , so $\vec{z}$ is the vector produced after two factors and the eigenvalue is the root belonging to the third factor, $b_3 = 2$ . Verify independently against the definition: the third entry of $A\vec{z}$ is $2(1) - 5(2) + 4(4) = 8$ .
$A [\begin{matrix} 1 \\ 2 \\ 4 \end{matrix}] = [\begin{matrix} 2 \\ 4 \\ 8 \end{matrix}] = 2 [\begin{matrix} 1 \\ 2 \\ 4 \end{matrix}]$
Reorder the factors and obtain a different eigenvalue
Apply $A - 2I_3$ first, then $A - I_3$ twice. The intermediate vectors are $(-2,0,2)$ and $(2,2,2)$ , and the third application collapses. Now $\vec{z} = (2,2,2)$ and the eigenvalue is $1$ : indeed $A(1,1,1) = (1,\ 1,\ 2 - 5 + 4) = (1,1,1)$ .
$(A - 2 I_{3}) \vec{x} = [\begin{matrix} - 2 \\ 0 \\ 2 \end{matrix}], (A - I_{3}) [\begin{matrix} - 2 \\ 0 \\ 2 \end{matrix}] = [\begin{matrix} 2 \\ 2 \\ 2 \end{matrix}], (A - I_{3}) [\begin{matrix} 2 \\ 2 \\ 2 \end{matrix}] = [\begin{matrix} 0 \\ 0 \\ 0 \end{matrix}]$

Result

Two runs of the same construction on the same matrix produced the eigenpairs $\left(2, (1,2,4)\right)$ and $\left(1, (1,1,1)\right)$ , differing only in the order the linear factors were applied. That is precisely what the theorem promises and no more: existence of at least one eigenvalue, with no claim about which one. For the filter, the eigenvalues $1$ and $2$ are the poles of its state recursion, both of magnitude at least one, so the unforced response does not decay — a conclusion reached here without ever writing down a determinant.

Applications & Industry Use

Numerical linear algebra

Krylov subspace eigenvalue solvers

The sequence built in the proof is the Krylov sequence, and the Arnoldi and Lanczos algorithms are that construction made numerically respectable: instead of using the power basis directly, they orthonormalise it as it is generated and extract eigenvalue estimates from the small projected matrix. Every large-scale sparse eigenvalue computation in engineering software descends from this argument.

Control systems

Controllability matrices and reachability

The controllability matrix of a state-space model is $\begin{bmatrix} \vec{b} & A\vec{b} & \cdots & A^{n-1}\vec{b} \end{bmatrix}$ — the Krylov sequence of the state matrix and the input direction. The dependence relation that the existence proof exploits is exactly the relation that limits the reachable subspace, and its degree is the dimension of the controllable subspace.

Signal processing

Prony's method and exponential fitting

Fitting a sum of damped exponentials to a sampled signal proceeds by finding a linear recurrence the samples satisfy, forming its characteristic polynomial and taking the roots as the exponential rates. Structurally this is the same construction: a forced linear dependence among shifted data vectors, converted into a polynomial whose roots are eigenvalues of the underlying shift operator.

Structural dynamics

Model order reduction

Reduced-order models of large finite element systems are built by projecting onto a Krylov subspace generated from the load vector. The moment-matching properties of these reduced models follow from the same annihilating-polynomial structure, and the degree at which the Krylov sequence becomes dependent bounds how far the reduction can usefully go.

Computational chemistry and physics

Extremal eigenvalues of very large operators

Ground-state energy calculations require the lowest eigenvalue of a matrix far too large to factor. Lanczos iteration builds the Krylov sequence implicitly through matrix-vector products and converges rapidly to the extremes of the spectrum, delivering the result the existence argument guarantees is there without ever forming the matrix in dense storage.

Systems identification

Minimal polynomials from measured responses

Given a measured impulse response, forming a Hankel matrix of samples and finding its null space produces the coefficients of the recurrence the system obeys. The roots of that polynomial are the system poles. The rank at which the Hankel matrix becomes deficient plays the role of the degree $m$ in the proof and is the identified model order.

Design Considerations

Do not treat the proof as an algorithm

The construction requires the roots of a polynomial of degree up to $n$ and uses the power basis $\vec{x}, A\vec{x}, A^{2}\vec{x}, \ldots$ , which becomes catastrophically ill conditioned as it lengthens because every vector converges towards the dominant eigendirection. Both defects are fatal beyond very small sizes. Use it to understand why eigenvalues exist, and use QR or Arnoldi to find them.

Expect the starting vector to matter

The polynomial produced is the annihilating polynomial of the chosen vector, which may have degree well below $n$ if that vector happens to lie in a small invariant subspace. Its roots are then only some of the eigenvalues. Choosing a vector with random entries makes a degenerate outcome improbable, which is exactly why Krylov solvers start from a random vector.

Order the factors deliberately if you want a particular eigenvalue

Which eigenvalue emerges depends on the order in which the linear factors are applied. Placing a suspected eigenvalue's factor last increases the chance that the construction returns it. This is not a robust targeting mechanism, but it explains why the same matrix and the same polynomial can yield different eigenpairs on different runs.

Keep the arithmetic complex

The factorisation step is the only one that requires $\mathbb{C}$ , and it is unavoidable. A real matrix can have a purely complex spectrum, and a real-arithmetic implementation of this construction will simply fail to find a factorisation. Where real arithmetic is mandatory, pair conjugate roots into real quadratic factors and work with the resulting invariant planes.

Recognise the numerical replacement for each step

The proof's three ingredients each have a stable counterpart. Building the Krylov sequence becomes Arnoldi or Lanczos with explicit reorthogonalisation. Finding the dependence becomes solving a small projected eigenproblem. Root-finding on a high-degree polynomial — notoriously unstable — is avoided entirely in favour of the shifted QR iteration on the small matrix.

Use existence as a licence, not as a promise of niceness

The theorem guarantees at least one eigenpair. It does not guarantee $n$ independent eigenvectors, well-separated eigenvalues, or eigenvectors that are numerically well determined. A matrix can have a single eigenvalue with a one-dimensional eigenspace, and a non-normal matrix can have eigenvectors so sensitive that they carry almost no usable information.

Standards & Codes

Notation, interchange and numerical standards that govern how this material is written down, stored and computed in production systems.

Applicable standards, conventions and reference implementations
Reference	Title	Relevance to this topic
`ISO 80000-2`	Quantities and units — Part 2: Mathematics	Fixes the notation for the complex field $\mathbb{C}$ , the identity matrix, matrix powers and the eigenvalue symbol $\lambda$ used in the statement and proof.
`LAPACK xGEHRD / xHSEQR`	Hessenberg reduction and QR eigenvalue iteration	The production replacement for the construction described here. Reduction to Hessenberg form followed by shifted QR is the numerically stable route to the eigenvalues whose existence this theorem guarantees.
`ARPACK / xNAUPD interface`	Implicitly restarted Arnoldi method	The direct engineering descendant of the Krylov sequence in the proof, with orthogonalisation and restarting added so that the power basis never becomes the ill-conditioned object the naive construction produces.
`IEEE 754-2019`	IEEE Standard for Floating-Point Arithmetic	Defines the complex arithmetic in which the factorisation step must be carried out, and the rounding behaviour that makes the raw Krylov power basis unusable after a modest number of terms.
`ISO 18431-2`	Mechanical vibration and shock — Signal processing, Fourier transforms	Frames the measured-response setting in which Prony-type identification recovers system poles by exactly the dependence-then-factor mechanism used in this proof.

Material Selection

For a mathematical topic, "material" is the numeric representation: the scalar field, storage format and precision the computation is built from.

Representation and precision selection
Representation	Select when	Trade-off
Exact rational arithmetic with symbolic root-finding	Small matrices where the annihilating polynomial and its exact roots are wanted, as in textbook verification or symbolic control design.	Delivers exact eigenvalues as algebraic numbers, but root-finding beyond degree four has no closed form and expression size grows quickly.
IEEE 754 binary64 complex arithmetic	Any numerical realisation of the construction, since the factorisation step requires complex roots even for real input.	Doubles storage and roughly quadruples multiplication cost relative to real arithmetic, but is unavoidable once complex eigenvalues are possible.
Power basis (the literal Krylov sequence)	Illustrative computation at very small sizes, or where the sequence terminates after two or three terms.	Trivial to implement, but the vectors align rapidly with the dominant eigendirection and the basis loses all conditioning after a handful of steps.
Orthonormalised Krylov basis (Arnoldi or Lanczos)	Any practical use of the construction on a matrix of realistic size.	Preserves conditioning and gives reliable eigenvalue estimates, at the cost of an orthogonalisation step per iteration and, in finite precision, the need for reorthogonalisation.
Sparse matrix-free operator	Very large problems where $A$ is available only as a routine computing $A\vec{v}$ , as in matrix-free finite element and physics codes.	Memory stays proportional to a few vectors and the method scales to enormous problems, but only a few eigenvalues at one end of the spectrum are obtainable.
Finite field arithmetic	Algebraic settings such as coding theory where the underlying scalars are not complex.	Exact and overflow-free, but the existence theorem itself fails: a polynomial need not factor into linear pieces over a finite field, so an extension field must be constructed first.

Manufacturing Notes

Implementation notes — how the result is actually produced by hand, by algorithm and by library, including cost and numerical behaviour.

Cost of the literal construction

Building the Krylov sequence takes $n$ matrix-vector products, about $2n^{3}$ operations for a dense matrix. Solving for the dependence relation is one row reduction of an $n \times (n+1)$ matrix, roughly $\tfrac{2}{3}n^{3}$ . Root-finding on a degree- $n$ polynomial is the expensive and unstable part. Total cost is comparable to a full QR eigenvalue solve, with far worse accuracy — which is the whole case against using it.

Hand procedure

Compute the Krylov vectors one at a time, each from the previous rather than by forming matrix powers. Row-reduce the array of Krylov vectors as columns and read a null space vector for the coefficients. Verify the dependence relation entry by entry before proceeding — an error here propagates into a polynomial whose roots are not eigenvalues at all, and the mistake will only surface at the final verification.

Where each step is replaced in practice

Modern software never follows these steps literally. LAPACK's xGEEV reduces to Hessenberg form and runs a shifted QR iteration; ARPACK and SciPy's scipy.sparse.linalg.eigs build an orthonormalised Krylov basis with implicit restarts. SymPy's Matrix.eigenvals() does follow a polynomial route, forming the characteristic polynomial exactly and factoring it symbolically, which is viable only because the arithmetic is exact.

Verification of the produced eigenpair

The construction is long enough that an independent check is essential. Compute $A\vec{z}$ directly and compare it with $b_k\vec{z}$ entry by entry. This test is completely independent of the polynomial work, so it catches an error in the dependence relation, in the factorisation or in the peeling with equal reliability.

Why the power basis fails numerically

Each application of $A$ amplifies the component along the dominant eigendirection relative to the others by the ratio of eigenvalue magnitudes. After a modest number of steps every Krylov vector is nearly parallel to that direction, so the computed basis is numerically rank-deficient and the dependence coefficients are meaningless. Orthogonalising each new vector against its predecessors as it is generated — the Arnoldi step — is the standard fix.

Failure Modes & Common Mistakes

Failure modes, root causes and prevention
Failure mode / mistake	Impact	Root cause	Prevention & detection
Starting from the zero vector	high	Overlooking the hypothesis $\vec{x} \ne \vec{0}$ , which makes every Krylov vector zero and the whole construction vacuous.	Assert the starting vector is non-zero. In code, generate it randomly and check its norm before proceeding.
Assuming the polynomial is the characteristic polynomial	medium	Treating the degree- $m$ annihilating polynomial as though $m = n$ and its roots were the whole spectrum.	Remember that an unlucky starting vector can give $m < n$ . Only the roots actually produced are certified eigenvalues; absence from the list proves nothing.
Attempting the factorisation over the reals	high	Implementing the construction in real arithmetic, so a matrix with a purely complex spectrum yields no linear factors and the proof stalls.	Use complex arithmetic throughout, or pair conjugate roots into real quadratic factors and work with the corresponding invariant planes.
Applying all the factors at once	medium	Forming the whole product $p(A)$ and multiplying by $\vec{x}$ , which gives the zero vector and identifies no particular eigenvalue.	Apply the factors sequentially and record the running vector after each one. The construction depends entirely on catching the first collapse.
Missing the argument that $m \ge 1$	low	Accepting a dependence relation in which only $a_0$ is non-zero, which would give a constant polynomial with no roots.	Note explicitly that $a_0\vec{x} = \vec{0}$ with $a_0 \ne 0$ and $\vec{x} \ne \vec{0}$ is impossible, so some coefficient of positive index must be non-zero.
Using the raw power basis at scale	high	Implementing the Krylov sequence literally, so the vectors align with the dominant eigendirection and the basis becomes numerically rank deficient.	Orthonormalise each new vector against its predecessors as it is generated, with reorthogonalisation when the norm drops sharply.
Root-finding on a high-degree polynomial in floating point	high	Extracting roots from the coefficients of a degree- $n$ polynomial, a notoriously ill-conditioned operation for large $n$ .	Never route a numerical eigenvalue computation through explicit polynomial coefficients. Use a matrix-based iteration such as shifted QR.
Concluding that the matrix is diagonalisable	medium	Reading the existence theorem as guaranteeing a full set of independent eigenvectors, which it does not.	Distinguish existence of one eigenpair from existence of an eigenbasis. Check the geometric multiplicities before assuming diagonalisability.

FAQs

Why does this proof avoid determinants, and does that matter?

The determinant route is perfectly valid but heavier: it needs the determinant to be defined, needs $\det(A - xI_n)$ to be a polynomial of degree $n$ , and needs the singularity criterion. The argument here uses only linear dependence and polynomial factorisation. Isolating those two ingredients shows precisely what the theorem rests on and makes it transportable to settings, such as operators on abstract vector spaces, where no determinant is available.

Why does the theorem fail over the real numbers?

The factorisation step is the only place where the field matters, and over $\mathbb{R}$ a polynomial need not factor into linear pieces — $z^{2}+1$ does not. Concretely, the quarter-turn rotation of the plane has the annihilating polynomial $z^{2}+1$ , with no real roots, and geometrically it leaves no real direction invariant. Over $\mathbb{C}$ its eigenvalues are $i$ and $-i$ .

Does the construction find all the eigenvalues?

No. It produces exactly one, determined by the starting vector and the ordering of the linear factors. If the starting vector happens to lie in a small invariant subspace, the annihilating polynomial can have degree well below $n$ and its roots will be only part of the spectrum. Establishing an upper bound of $n$ on the number of distinct eigenvalues is a separate result.

Why must the vector

\vec{z}

be non-zero?

Because $k$ was chosen as the smallest index at which the accumulated product of factors annihilates $\vec{x}$ . The vector $\vec{z}$ is what the first $k-1$ factors produce, and if it were zero then $k-1$ would already have that property, contradicting minimality. When $k = 1$ no factors have been applied and $\vec{z} = \vec{x}$ , which is non-zero by hypothesis.

Is the annihilating polynomial unique?

No. Any non-trivial dependence relation among the Krylov vectors gives one, and any multiple of an annihilating polynomial is also annihilating. There is a unique monic annihilating polynomial of least degree for a given vector — the minimal polynomial of that vector — and every other annihilating polynomial for it is a multiple of that one.

How is this related to Krylov subspace methods?

Directly. The sequence $\vec{x}, A\vec{x}, \ldots, A^{n}\vec{x}$ is the Krylov sequence, and the forced dependence at step $n+1$ is what bounds the dimension of the Krylov subspace. Arnoldi and Lanczos build the same subspace but orthonormalise the basis as they go, and they extract eigenvalue estimates from a small projected matrix instead of from polynomial coefficients — keeping the mathematics and discarding the numerical defects.

Should I ever compute an eigenvalue this way?

Only for demonstration on a small matrix with exact arithmetic. The power basis loses conditioning within a few steps, and finding the roots of a degree- $n$ polynomial from its coefficients is ill-conditioned even when the eigenvalues themselves are well separated. Production eigenvalue computation uses Hessenberg reduction with shifted QR for dense matrices and restarted Arnoldi or Lanczos for sparse ones.

References

Beezer, R. A. A First Course in Linear Algebra, Version 0.70. University of Puget Sound, 2006. Section EE, Subsection EEE. Licensed under the GNU Free Documentation License v1.2.
Axler, S. Linear Algebra Done Right, 3rd edition. Springer, 2015. Chapter 5, the determinant-free existence argument.
ISO 80000-2:2019, Quantities and units — Part 2: Mathematics. International Organization for Standardization.
Saad, Y. Numerical Methods for Large Eigenvalue Problems, revised edition. Society for Industrial and Applied Mathematics, 2011.
Golub, G. H. and Van Loan, C. F. Matrix Computations, 4th edition. Johns Hopkins University Press, 2013.

AI Suggested Questions

Run this construction on a $3 \times 3$ real matrix with a complex conjugate pair of eigenvalues, and show where real arithmetic would break down.
Show a starting vector for which the annihilating polynomial has degree strictly less than the matrix size, and explain which eigenvalues are then invisible to the construction.
Quantify how quickly the Krylov power basis loses conditioning as a function of the ratio between the two largest eigenvalue magnitudes.
Compare this existence proof with the determinant-based one, identifying exactly which hypotheses each argument uses.
Explain how the Arnoldi algorithm turns this construction into a numerically stable method, step by corresponding step.
Why is finding polynomial roots from coefficients ill-conditioned, and how does the shifted QR iteration avoid the problem entirely?

Related Calculators

Krylov Sequence Explorer

Generate $\vec{x}, A\vec{x}, \ldots, A^{n}\vec{x}$ for a chosen matrix and starting vector, and find the dependence relation among them.

Annihilating Polynomial Finder

Compute the minimal annihilating polynomial of a vector with respect to a matrix, factor it, and peel the factors to extract an eigenpair.

Eigenvalue & Eigenvector Calculator

Compute the full spectrum of a square matrix with eigenvectors, multiplicities and residual checks.