How do I diagonalize matrix A?

How it works

Reading the cells. A cell typed as a decimal with up to 15 significant digits is that decimal exactly: 0.8 is 4/5. A cell typed as a fraction such as 1/3 reaches the page as a rounded number; it is read as the fraction with the smallest denominator (up to 1,000,000) that rounds to the same number.

Eigenvalues. The characteristic polynomial det(λI − A) comes from the Faddeev-LeVerrier recurrence in exact fractions. Its fraction roots are found as on the characteristic polynomial calculator: the page takes the square-free part s = p ÷ gcd(p, p′) (exact), whose zeros are those of p, each once. While s has degree 2 or more, it finds the complex roots of s numerically (Durand-Kerner iteration, 800 rounds, starting on a circle whose radius is Fujiwara’s bound 2 × max |aₙ₋ₖ/aₙ|^(1/k), with a₀ halved). For each root whose imaginary part is within 10⁻⁷ × max(1, |real part|) of 0, it tries in turn the convergents of the continued fraction of the real part that lie within 10⁻³ × max(1, |root|) of it, with denominators up to 10¹²; a convergent r is a zero when s divided by (λ − r) leaves remainder exactly 0. Then s is divided by (λ − r) and the roots are found again. Before this, each diagonal entry of A is tried the same way, so a triangular matrix always gets its eigenvalues exactly. When s has degree 1, its zero −s₀/s₁ is a fraction. The multiplicity k of r is the number of times λ − r divides the polynomial exactly. If some part q of the polynomial has no root found as a fraction, the page gives no P and D and says "No verified answer: no fraction with a denominator up to 10¹² was found as a root of q (its roots may be irrational, complex, or fractions with larger denominators), so P and D cannot be given in exact fractions."

Eigenvectors. For each eigenvalue r, from smallest to largest, the page reduces A − rI to reduced row echelon form by Gauss-Jordan elimination in fractions. Each column with no pivot is a free variable; setting it to 1 and the other free variables to 0 gives one basic solution of (A − rI)v = 0. If there are fewer basic solutions than k, A is not diagonalizable and the page says which eigenvalue fails. Otherwise each basic solution is multiplied by the least common multiple of its denominators and divided by the greatest common divisor of its entries, so it has whole-number entries with no common factor.

P, D and P⁻¹. P has these vectors as columns, eigenvalue by eigenvalue, free variables from left to right. D is diagonal with each column’s eigenvalue. P⁻¹ comes from Gauss-Jordan elimination on [P | I]. The page checks A P = P D and P P⁻¹ = I exactly.

How answers are written

• Diagonalizable?: "Diagonalizable: A = P D P⁻¹", or "Not diagonalizable: the eigenvalue r is a root k times but has only m independent eigenvector(s)."
• P, D, P⁻¹: matrices in brackets, entries in a row separated by commas, rows separated by semicolons, entries as exact fractions in lowest terms: [−1/4, 1/2, 1/4; 1/2, 1, 1/2; …].

Assumptions

• Cells are exact: 0.1 is 1/10 and 1/3 is 1/3.
• Only eigenvalues that are fractions are handled; a matrix with irrational or complex eigenvalues gets a message, not decimals. A fraction eigenvalue with a denominator over about 10⁷ that is not a diagonal entry can be missed; the message then says so.

Worked examples by hand

A = [2, 0, 0; 1, 4, −1; −2, −4, 4] (Kuttler, A First Course in Linear Algebra, section 7.2, Example 7.2.1). det(λI − A) = (λ − 2)((λ − 4)² − 4) = (λ − 2)²(λ − 6). For λ = 2, A − 2I reduces to the one row [1, 2, −1], with free variables y and z: y = 1 gives (−2, 1, 0) and z = 1 gives (1, 0, 1). For λ = 6, A − 6I reduces to x = 0, y + z/2 = 0, so z = 1 gives (0, −1/2, 1), scaled to (0, −1, 2). So P = [−2, 1, 0; 1, 0, −1; 0, 1, 2] and D = [2, 0, 0; 0, 2, 0; 0, 0, 6]. The book’s third column is (0, 1, −2), the same eigenvector times −1.

A = [1, 1; 0, 1] (Example 7.2.2). det(λI − A) = (λ − 1)², so 1 is an eigenvalue twice, but A − I = [0, 1; 0, 0] has one free variable, so one basic solution (1, 0): not diagonalizable.