Fact-checked by Grok 2 weeks ago

Diagonalization

Diagonalization is a fundamental technique in mathematics with applications across various fields, including linear algebra, set theory, logic, and computability theory.^[1] In linear algebra, diagonalization refers to decomposing a square matrix A into the form A = PDP^{-1}, where P is an invertible matrix whose columns are the eigenvectors of A, and D is a diagonal matrix containing the corresponding eigenvalues on its main diagonal.^[2] This process simplifies computations such as matrix powers A^k = PD^k P^{-1}, with applications in dynamical systems, Markov chains, and differential equations.^[2]^[3] A matrix is diagonalizable if it has a full set of n linearly independent eigenvectors for size n \times n, which holds when the geometric multiplicity equals the algebraic multiplicity for each eigenvalue; matrices with distinct eigenvalues are always diagonalizable.^[2]^[4] In set theory, diagonalization is exemplified by Georg Cantor's diagonal argument, which demonstrates that the set of real numbers is uncountable by constructing a number differing from each in a supposed enumeration.^[5] In logic and proof theory, the diagonal lemma (or fixed-point theorem) guarantees the existence of self-referential sentences in formal systems, underpinning Gödel's incompleteness theorems.^[6] In computability theory, diagonalization arguments, such as those used in proofs of the halting problem's undecidability, show limitations of Turing machines and recursive functions.^[7] Diagonalization also appears in other areas, such as functional analysis. Not all linear transformations admit diagonalization over the complex numbers—defective matrices require the Jordan canonical form—but the technique preserves essential properties under basis changes.^[8]

Overview and History

General Concept

Diagonalization refers to a versatile method in mathematics and logic for simplifying representations of complex objects or demonstrating limitations through self-referential constructions. At its core, it leverages indexing or positional correspondence—often visualized as a "diagonal" in an array of elements—to pair components and generate distinctions that either reduce structures to a canonical diagonal form or produce counterexamples contradicting assumptions about completeness or decidability. This technique unifies diverse applications by exploiting enumeration and self-reference to achieve simplification or impossibility results.^[9] In linear algebra, diagonalization transforms a square matrix into an equivalent diagonal matrix through a similarity transformation, where the diagonal entries correspond to eigenvalues, thereby facilitating easier analysis of matrix properties and powers. For instance, a matrix representing a linear transformation can be diagonalized if it has a full set of linearly independent eigenvectors, allowing computations that would otherwise be cumbersome.^[2] In logic and set theory, diagonalization constructs a sequence or object that differs from every element in a given list at the position indexed by that element's place, often leading to proofs of uncountability or undecidability. A classic example is enumerating all possible infinite sequences and forming a new sequence that mismatches each one along the diagonal positions, revealing that no such enumeration can be exhaustive. This approach, pioneered by Georg Cantor, highlights the power of diagonal methods in revealing infinities of different sizes.^[10]

Historical Origins

The origins of diagonalization trace back to early 19th-century efforts in real analysis to rigorize concepts of convergence for infinite series and sequences. Mathematicians such as Bernard Bolzano, Augustin-Louis Cauchy, and Karl Weierstrass developed diagonal processes to handle double limits and extract convergent subsequences from bounded sequences, particularly in the context of the Bolzano-Weierstrass theorem, which ensures the existence of limit points in compact sets.^[11] These techniques addressed challenges in establishing uniform convergence and continuity for functions defined by infinite processes, laying foundational tools for later abstract arguments.^[11] In linear algebra, diagonalization emerged from studies of quadratic forms and transformations. Joseph-Louis Lagrange's work on the reduction of quadratic forms, as in his 1775 Recherches d'Arithmétique, provided early insights into simplifying multivariable expressions, while his 1788 Mécanique Analytique introduced principal axes through orthogonal transformations for the inertia tensor.^[12] This work influenced James Joseph Sylvester, who in the 1850s introduced concepts akin to eigenvalues while developing methods to diagonalize symmetric matrices and bilinear forms, emphasizing canonical multipliers.^[13] The full formalization arrived with Camille Jordan's 1870 treatise on substitution groups, where he established the Jordan canonical form, enabling the decomposition of matrices into diagonalizable blocks under similarity transformations for non-defective cases.^[14] A pivotal advancement occurred in set theory with Georg Cantor's 1891 diagonal argument, published in his paper "Über eine elementare Frage der Mannigfaltigkeitslehre," which demonstrated the uncountability of the real numbers by constructing a number differing from every element in a purported countable listing.^[15] David Hilbert's 1904 address "Über das Unendliche" and related problems spurred developments in proof theory, advocating finitary methods to secure mathematics' foundations and indirectly fostering diagonal techniques for analyzing formal systems' limitations.^[16] These ideas culminated in logic and computability: Kurt Gödel's 1931 incompleteness theorems employed a diagonal lemma to encode self-referential statements, proving that sufficiently powerful axiomatic systems cannot prove their own consistency.^[17] In 1936, Alonzo Church extended undecidability results via lambda calculus in his analysis of elementary number theory problems,^[18] while Alan Turing's diagonal argument in "On Computable Numbers" showed the existence of uncomputable functions, equating mechanical processes to Turing machine simulations.^[19]

Linear Algebra

Eigenvalues and Eigenvectors

In linear algebra, an eigenvalue \lambda of a square matrix A is a scalar that satisfies the equation Av = \lambda v, where v is a nonzero vector known as the corresponding eigenvector.^[20] This relationship indicates that the linear transformation represented by A scales the eigenvector v by \lambda without altering its direction.^[21] The term "eigen" derives from German, meaning "own" or "characteristic," reflecting the intrinsic scaling factor associated with each eigenvector.^[20] To compute eigenvalues, one solves the characteristic equation \det(A - \lambda I) = 0, where I is the identity matrix, yielding the characteristic polynomial whose roots are the eigenvalues.^[22] The algebraic multiplicity of an eigenvalue \lambda is the multiplicity of \lambda as a root of this polynomial, while the geometric multiplicity is the dimension of the eigenspace, i.e., the nullity of A - \lambda I.^[23] Once eigenvalues are found, eigenvectors are obtained by solving the homogeneous system (A - \lambda I)v = 0 for each \lambda, ensuring v \neq 0.^[24] Key properties of eigenvalues include that the trace of A, which is the sum of its diagonal entries, equals the sum of all eigenvalues (counting algebraic multiplicities), and the determinant of A equals the product of the eigenvalues (also counting multiplicities).^[25] For real matrices, nonreal eigenvalues occur in complex conjugate pairs, and their corresponding eigenvectors also form conjugate pairs.^[26] A diagonal matrix D with diagonal entries d_1, d_2, \dots, d_n has eigenvalues exactly equal to these entries, and the standard basis vectors serve as eigenvectors.^[27] In contrast, a 2×2 rotation matrix by angle \theta \neq k\pi (for integer k) has no real eigenvalues, as its characteristic polynomial \lambda^2 - 2\cos\theta \, \lambda + 1 = 0 yields complex roots \cos\theta \pm i \sin\theta.^[28]

Diagonalizable Matrices

A square matrix A \in \mathbb{R}^{n \times n} (or over any field) is diagonalizable if there exists an invertible matrix P and a diagonal matrix D such that A = P D P^{-1}, where the diagonal entries of D are the eigenvalues of A and the columns of P are corresponding eigenvectors of A.^[2]^[4] To derive this similarity transformation, suppose A has eigenvalues \lambda_1, \dots, \lambda_n with corresponding linearly independent eigenvectors v_1, \dots, v_n. Let P = [v_1 \ \dots \ v_n] and D = \operatorname{diag}(\lambda_1, \dots, \lambda_n). Then, for each i, A v_i = \lambda_i v_i, so multiplying on the left by P yields A P = P D. Since P is invertible, right-multiplying both sides by P^{-1} gives A = P D P^{-1}.^[29]^[30] A matrix A is diagonalizable if and only if, for every eigenvalue \lambda, the algebraic multiplicity of \lambda (the multiplicity as a root of the characteristic polynomial \det(A - \lambda I) = 0) equals the geometric multiplicity of \lambda (the dimension of the eigenspace \ker(A - \lambda I)). Equivalently, A is diagonalizable if and only if its minimal polynomial factors into distinct linear factors over the base field.^[2]^[31]^[32] The process of diagonalizing a matrix A begins by solving the characteristic equation \det(A - \lambda I) = 0 to find the eigenvalues \lambda_1, \dots, \lambda_k. For each \lambda_i, solve (A - \lambda_i I) v = 0 to find a basis for the eigenspace, ensuring the total number of linearly independent eigenvectors is n; if not, A is not diagonalizable. Form P with these eigenvectors as columns and D with the eigenvalues on the diagonal corresponding to each column of P. Verify the diagonalization by computing P D P^{-1} and checking that it equals A.^[2]^[33] A key example is that every real symmetric matrix is diagonalizable, as guaranteed by the spectral theorem, which states that such a matrix has n real eigenvalues (counting multiplicities) and an orthonormal basis of eigenvectors.^[34]^[35]

Jordan Canonical Form

The Jordan canonical form, also referred to as the Jordan normal form, serves as a generalization of diagonalization for square matrices over an algebraically closed field, such as the complex numbers, that do not admit a full basis of eigenvectors. Every such matrix A is similar to a unique (up to permutation of blocks) block diagonal matrix J, known as the Jordan form, which consists of Jordan blocks along the diagonal. A Jordan block of size m \times m corresponding to an eigenvalue \lambda is an upper triangular matrix with \lambda on the main diagonal and 1's on the superdiagonal, with all other entries zero; this structure captures the matrix's action on chains of generalized eigenvectors. This representation was first established by Camille Jordan in his comprehensive 1870 treatise on substitutions and algebraic equations.^[36]^[37] The construction of the Jordan form proceeds by partitioning the vector space into generalized eigenspaces, one for each distinct eigenvalue \lambda. The generalized eigenspace for \lambda is defined as the kernel of (A - \lambda I)^n, where n is the dimension of the space, and it decomposes into invariant subspaces corresponding to the Jordan blocks for that eigenvalue. Within each generalized eigenspace, a basis is formed by selecting chains of generalized eigenvectors: starting from an eigenvector v_1 satisfying (A - \lambda I)v_1 = 0, subsequent vectors v_2, \dots, v_m satisfy (A - \lambda I)v_{k+1} = v_k for k = 1, \dots, m-1, until the chain length matches the block size. The collection of all such basis vectors across eigenvalues yields an invertible matrix P such that J = P^{-1} A P, where J is block diagonal with the Jordan blocks. The sizes of these blocks are determined by the differences in dimensions of the kernels of (A - \lambda I)^k for increasing k, specifically, the number of blocks of size at least k is \dim \ker (A - \lambda I)^k - \dim \ker (A - \lambda I)^{k-1}.^[37] This form is particularly useful when the geometric multiplicity of an eigenvalue (the dimension of its eigenspace, \dim \ker (A - \lambda I)) is strictly less than its algebraic multiplicity (the multiplicity in the characteristic polynomial), as this deficiency prevents full diagonalization and necessitates Jordan blocks larger than $1 \times 1. For instance, consider the $2 \times 2 matrix A = \begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix}, which has a repeated eigenvalue \lambda but geometric multiplicity 1, since the eigenspace is spanned by only one independent eigenvector; its Jordan form is itself, illustrating a single $2 \times 2 block. In the special case where all Jordan blocks are $1 \times 1, the form coincides with the diagonalizable case discussed earlier.^[37] The explicit similarity transformation is given by

A = P J P^{-1},

where the columns of P are the generalized eigenvectors forming the chains, and J has the block structure

J = \begin{pmatrix} J_{m_1}(\lambda_1) & & \\ & \ddots & \\ & & J_{m_r}(\lambda_r) \end{pmatrix},

with each J_m(\lambda) denoting a m \times m Jordan block for eigenvalue \lambda. This canonical structure facilitates the analysis of matrix powers, exponentials, and solutions to linear differential equations involving A, as powers of J preserve the block form with binomial coefficients on the superdiagonals.^[37]

Set Theory

Cantor's Diagonal Argument

Cantor's diagonal argument, presented in his 1891 paper, demonstrates that the set of real numbers in the interval (0,1) is uncountable by assuming the contrary and deriving a contradiction.^[10] Suppose, for the sake of contradiction, that these real numbers are countable, so they can be enumerated as a sequence r_1, r_2, r_3, \dots, where each r_n is expressed via its decimal expansion r_n = 0.d_{n1} d_{n2} d_{n3} \dots, with each digit d_{nj} an integer from 0 to 9.^[38] To construct a real number not in this list, form a new decimal expansion \alpha = 0.d_1 d_2 d_3 \dots, where the diagonal digits are altered such that d_n \neq d_{nn} for each n. One common choice is to set d_n = 4 if d_{nn} \neq 4 and d_n = 5 if d_{nn} = 4, ensuring \alpha differs from r_n in the n-th decimal place for every n. Thus, \alpha cannot equal any r_n, contradicting the assumption that the list includes all reals in (0,1). This establishes uncountability.^[10] In matrix notation, let S = (s_{i,j}) be the infinite matrix of digits where rows correspond to the enumerated reals and columns to decimal places, so s_{i,j} = d_{ij}. The diagonal sequence is defined by d_n \neq s_{n,n} for all n, yielding \alpha outside the enumeration.^[38] Decimal expansions are not always unique, as some reals have dual representations (e.g., $0.4999\dots = 0.5000\dots), potentially allowing the constructed \alpha to match an existing expansion ending in infinite 9s or 0s. To circumvent this, the digit choice avoids 0 and 9 (e.g., using 1 and 2 instead of 4 and 5), ensuring \alpha has no terminating expansion and thus remains distinct. The argument formalizes similarly for infinite binary sequences, representing subsets of the natural numbers or points in the Cantor set. Assume all binary sequences b_1, b_2, \dots where each b_n = 0.b_{n1} b_{n2} b_{n3} \dots with b_{nj} \in \{0,1\}. Construct \beta = 0.b_1 b_2 b_3 \dots by setting b_n = 1 - b_{nn}, so \beta differs from each b_n in the n-th position, proving the set of binary sequences uncountable. Another formalization uses continued fraction expansions, which provide unique representations for irrational numbers. Each real in (0,1) has a continued fraction [0; a_1, a_2, a_3, \dots ] with positive integers a_i \geq 1. Assuming an enumeration, construct a new fraction by setting the n-th partial quotient to differ from the n-th in the list (e.g., a_n' = a_{nn} + 1), yielding a distinct real and the same contradiction.^[39]

Implications for Cardinality

The diagonal argument establishes that the real numbers form an uncountable set, implying no bijection exists between the natural numbers and the reals, so the cardinality of the reals satisfies |\mathbb{R}| > \aleph_0.^[10] This cardinality, known as the continuum, is denoted $2^{\aleph_0}, representing the size of the power set of the naturals.^[10] Cantor's theorem generalizes this result, proving that for any set S, the power set \mathcal{P}(S) has strictly greater cardinality than S, i.e., |\mathcal{P}(S)| > |S|.^[10] The proof employs diagonalization applied to the characteristic functions of subsets of S, constructing an element not in any listed subset to show the injection from S to \mathcal{P}(S) cannot be surjective.^[10] This theorem holds for finite and infinite sets alike, underscoring the strict inequality in cardinalities.^[10] Iterating the power set operation yields a transfinite hierarchy of cardinals, with each level larger than the previous: \aleph_0 < 2^{\aleph_0} \leq 2^{2^{\aleph_0}} \leq 2^{2^{2^{\aleph_0}}} \leq \cdots.^[10] In cardinal arithmetic, exponentiation $2^\kappa for infinite cardinal \kappa always exceeds \kappa, ensuring this strict progression without bound.^[10] These implications bear on the continuum hypothesis (CH), which asserts $2^{\aleph_0} = \aleph_1, meaning no cardinal lies between \aleph_0 and the continuum. CH remains unsolved within Zermelo-Fraenkel set theory with the axiom of choice (ZFC), as Gödel demonstrated its consistency relative to ZFC in 1940,^[40] and Cohen proved its independence from ZFC in 1963 using forcing.^[41]

Logic and Proof Theory

The Diagonal Lemma

The diagonal lemma, also known as the fixed-point theorem or theorem on self-reference, states that in a formal system F capable of representing recursive functions and equipped with a Gödel numbering, for any formula \phi(x) with one free variable x, there exists a sentence \psi such that F proves \psi \leftrightarrow \phi(\ulcorner \psi \urcorner), where \ulcorner \psi \urcorner denotes the Gödel number (or numeral) of \psi.^[6] This result was implicitly employed by Kurt Gödel in his 1931 proof of incompleteness,^[42] though the general version was not explicitly isolated as a separate lemma until Rudolf Carnap's work in 1934.^[17] A proof sketch proceeds as follows. Define a diagonalization function \textit{diag}(x) that substitutes the numeral for x's own Gödel number into the formula with code x, yielding \textit{diag}(x) = \textit{subst}(x, \ulcorner x \urcorner), where \textit{subst}(u, v) is the arithmetized substitution function replacing the free variable in the formula coded by u with the numeral for v.^[6] This function is representable in F by a formula D(y, z) such that F \vdash D(\ulcorner t \urcorner, \ulcorner \textit{diag}(t) \urcorner) for any term t. Consider the formula \theta(x) = \phi(\textit{diag}(x)); let \ulcorner \theta \urcorner = \boldsymbol{n}. Then the sentence \psi = \theta(\underline{n}) satisfies \psi \leftrightarrow \phi(\ulcorner \psi \urcorner), as \ulcorner \psi \urcorner = \textit{diag}(\boldsymbol{n}) by construction, and F proves the equivalence via the representability of substitution and the uniqueness of Gödel numbers.^[43] The lemma facilitates controlled self-reference within formal systems, allowing sentences to "talk about themselves" syntactically through their codes, without generating paradoxes akin to the liar paradox in natural language, because the system's soundness ensures that the biconditional holds without contradiction.^[44] For instance, taking \phi(x) to express "x is not provable in F" (representable via the provability predicate), the resulting \psi is the Gödel sentence, which asserts its own unprovability and is true but neither provable nor refutable in F assuming consistency.^[6] Formally, the lemma relies on the strong representability of primitive recursive functions, including substitution and Gödel numbering, within arithmetical theories like Peano arithmetic, ensuring that the diagonal construction is provably correct inside the system itself.^[43]

Applications in Incompleteness Theorems

The diagonal lemma provides a crucial tool for constructing self-referential sentences within formal systems capable of expressing basic arithmetic, enabling the proof of Gödel's first incompleteness theorem.^[17] Specifically, for a consistent formal system F containing Robinson arithmetic Q, the lemma yields a Gödel sentence G_F such that F \vdash G_F \leftrightarrow \neg \Prov_F(\ulcorner G_F \urcorner), where \Prov_F(x) is the formalization of "there exists a proof in F of the formula with Gödel number x", and \ulcorner G_F \urcorner denotes the Gödel number of G_F.^[17] If F is consistent, then F \not\vdash G_F, since assuming a proof of G_F would imply a proof of a contradiction via the equivalence.^[17] Moreover, under the assumption of \omega-consistency (a strengthening of consistency ensuring that the system does not prove false existential statements about natural numbers), F \not\vdash \neg G_F, rendering G_F true in the standard model but unprovable in F.^[17] Thus, any such consistent system is incomplete, as there exist sentences that are true but neither provable nor refutable within it. This incompleteness arises from the arithmetization of syntax via Gödel numbering, which assigns unique natural numbers to formulas, proofs, and derivations in F, allowing syntactic notions like provability to be expressed as arithmetic predicates.^[17] For example, a proof in F is encoded by sequencing the Gödel numbers of its axioms and inference steps, ensuring that the relation \Prov_F(x) captures the existence of such a sequence for x = \ulcorner \phi \urcorner.^[17] Applying the diagonal lemma to \neg \Prov_F(x) self-referentially produces G_F, which intuitively states "I am not provable in F", and its unprovability follows directly from consistency. The diagonal lemma extends to Gödel's second incompleteness theorem, demonstrating that if F is consistent, it cannot prove its own consistency.^[17] Here, consistency is formalized as \Cons(F) \equiv \neg \Prov_F(\ulcorner \bot \urcorner), where \bot denotes a contradiction like $0=1.^[17] By the first theorem, F \vdash G_F \leftrightarrow \Cons(F), since \neg \Prov_F(\ulcorner G_F \urcorner) is equivalent to the consistency statement under the derivability conditions for \Prov_F.^[17] Thus, assuming F \vdash \Cons(F) would imply F \vdash G_F, contradicting the consistency of F by the first theorem.^[17] This result holds for systems satisfying Löb's derivability conditions and containing enough arithmetic, without needing \omega-consistency beyond the first theorem's setup.^[17] These theorems reveal fundamental limits to formalization, showing that no consistent axiomatic system encompassing arithmetic can capture all mathematical truths or verify its own reliability internally.^[17] They decisively impacted Hilbert's program, which sought a finitary proof of the consistency of mathematics, by proving such a proof impossible within the systems themselves.

Computability and Other Areas

Diagonalization in Turing Machines

In computability theory, diagonalization provides a powerful technique to demonstrate the existence of undecidable problems for Turing machines, most notably in Alan Turing's seminal proof that the halting problem is undecidable.^[19] The halting problem asks whether there exists a Turing machine that, given the description of another Turing machine M and an input w, can determine if M halts on w. Turing showed that no such general decider exists, using a diagonal argument to construct a machine that leads to a logical contradiction.^[19] To establish this, assume for contradiction that a Turing machine H decides the halting problem: on input \langle M, w \rangle (where \langle \cdot, \cdot \rangle denotes a standard encoding pairing the description of M with w), H halts and accepts if M halts on w, and rejects otherwise.^[45] Using H, construct a new Turing machine D that, on input x, simulates H on \langle D, x \rangle: if H accepts (indicating D would halt on x), then D enters an infinite loop; if H rejects (indicating D would loop on x), then D halts immediately.^[45] This construction ensures D's behavior on any input x is the opposite of what H predicts for D itself on that input. Now consider D applied to its own description \langle D, \langle D \rangle \rangle: if H(D, \langle D \rangle) accepts, predicting that D halts on \langle D \rangle, then D loops by construction, yielding a contradiction; conversely, if H rejects, predicting that D loops on \langle D \rangle, then D halts, again a contradiction.^[19] Therefore, no such H can exist, proving the halting problem undecidable. This self-referential contradiction mirrors the diagonal lemma in logic but applies here to algorithmic behavior.^[45] Formally, the argument can be viewed through an infinite table where rows and columns index all Turing machines and inputs, with entries indicating whether the machine halts (say, 1) or loops (0) on that input.^[46] A decider H would fill this table completely, but the diagonal machine D is constructed to flip the entries along the main diagonal (its own row), ensuring D differs from every machine in the table, including itself if H existed—thus, no complete table is possible.^[46] This result generalizes to show that no Turing machine can decide its own language: if a universal machine U could decide the language of an arbitrary machine M (i.e., L(M) = \{ w \mid M \ accepts \ w \}), then by diagonalization, a machine differing from U's prediction on its own inputs leads to contradiction.^[47] Consequently, the halting problem's undecidability implies many others via reduction; for example, the blank-tape halting problem (determining if a Turing machine halts when started on empty input) is undecidable, since the general halting problem reduces to it: given M and w, construct M' that on empty input simulates M on w and halts iff it does.^[45] Such reductions establish uncomputability for problems like Rice's theorem applications, where any non-trivial property of the language of a Turing machine is undecidable.^[47]

Diagonalization in Functional Analysis

In functional analysis, diagonalization of operators on infinite-dimensional Hilbert spaces is primarily achieved through the spectral theorem for compact self-adjoint operators. For a compact self-adjoint operator T on a separable Hilbert space H, the spectrum consists of real eigenvalues \{\lambda_n\} (possibly accumulating only at 0), each with a finite-dimensional eigenspace except possibly for the kernel, and the union of these eigenspaces is dense in H. There exists an orthonormal basis \{e_n\} of H composed of eigenvectors of T, extending the finite-dimensional case where every self-adjoint operator is unitarily diagonalizable.^[48]^[49] This basis enables the explicit diagonal representation of the operator as

T x = \sum_{n=1}^\infty \lambda_n \langle x, e_n \rangle e_n, \quad x \in H,

where the inner product \langle \cdot, \cdot \rangle is the Hilbert space inner product, allowing T to act as multiplication by the sequence \{\lambda_n\} in the eigenbasis. The eigenvalues satisfy |\lambda_1| \geq |\lambda_2| \geq \cdots \to 0 when countably infinite, and the null space admits its own orthonormal basis to complete the full basis of H. This form facilitates the construction of functions of T, such as resolvents or exponentials, via the same series.^[48] Not all operators on infinite-dimensional Hilbert spaces admit such diagonalization. Bounded self-adjoint operators may have continuous spectrum without point eigenvalues, as in the multiplication operator by x on L^2([0,1]), precluding an orthonormal eigenbasis. The unilateral shift operator on \ell^2(\mathbb{N}), defined by (S e_n) = e_{n+1} for the standard basis \{e_n\}, is bounded but has empty point spectrum, rendering it non-diagonalizable via eigenvectors. In these scenarios, the broader spectral theorem employs spectral measures or projections to decompose the operator, often requiring generalized eigenspaces for non-normal cases.^[50] Key applications include quantum mechanics, where the spectral theorem diagonalizes self-adjoint Hamiltonians H, yielding discrete energy eigenvalues and orthonormal eigenstates that describe bound states and dynamics via the time evolution e^{-itH}. For instance, in many-body systems, it determines ground state energies like \inf \sigma(H_N) = 4\pi a N + o(N) for Bose-Einstein condensation models. In Fourier analysis, the theorem supports decompositions of translation-invariant operators, such as the Laplacian on L^2(\mathbb{R}^n), into multiplication operators in the frequency domain. A concrete example is the negative Laplacian -\Delta on L^2(M) for a compact Riemannian manifold M, where eigenfunctions \{\phi_j\} satisfy -\Delta \phi_j = \mu_j \phi_j with \mu_j \to \infty, forming an orthonormal basis; on the sphere S^n, these are spherical harmonics with eigenvalues \ell(\ell + n - 1) for degree \ell. On L^2(\mathbb{R}^n), plane waves e^{i \xi \cdot x} serve as generalized eigenfunctions with continuous eigenvalues |\xi|^2, enabling solutions to PDEs like the heat or wave equation.^[51]^[52]^[53]

References

[1]
Diagonalization
Diagonal matrices are the easiest kind of matrices to understand: they just scale the coordinate directions by their diagonal entries. In Section 5.3, we saw ...
[2]
Math 2331 – Linear Algebra - 5.3 Diagonalization
Diagonalizable. A square matrix A is said to be diagonalizable if A is similar to a diagonal matrix, i.e. if A = PDP-1 where P is invertible and D is a diagonal ...
[3]
[PDF] 5.3 Diagonalization - UC Berkeley math
Theorem 5 (The Diagonalization Theorem). An n × n matrix A is diagonalizable if and only if A has n linearly independent eigenvectors. In fact, A = P−1DP ...Missing: mathematics | Show results with:mathematics
[4]
[PDF] Notes on Eigenvalues, eigenvectors, and diagonalization
Terminology: The process of finding the P and the D such that P−1AP = D is called diagonalization. If it is possible to diagonalize A (in other words, if there ...
[5]
3. Determinants and Diagonalization - Emory Mathematics
Apr 2, 2011 · These eigenvalues are essential to a technique called diagonalization that is used in many applications where it is desired to predict the ...
[6]
[PDF] Unit 16: Diagonalization
LINEAR ALGEBRA AND VECTOR ANALYSIS. MATH 22B. Unit 16: Diagonalization. Lecture. 16.1. We say that B = {v1,v2,··· ,vn} is an eigenbasis of a n × n matrix A if ...
[7]
[PDF] Math 240: Diagonalization
Feb 3, 2011 · An n × n matrix A is diagonalizable if there exists an n × n invertible matrix P and an n × n diagonal matrix D such that P−1AP = D.
[8]
[PDF] Diagonalization of Matrices
Definition 14.3. An n × n matrix A is diagonalizable if there is an invertible n × n matrix C such that C−1AC is a diagonal matrix. The matrix C is said to ...
[9]
Diagonalization and the recursion theorem. - Project Euclid
January 1973 Diagonalization and the recursion theorem. James C. Owings Jr. Notre Dame J. Formal Logic 14(1): 95-99 (January 1973). DOI: 10.1305/ndjfl ...
[10]
[PDF] Ueber eine elementare Frage der Mannigfaltigketislehre. (7 Seiten)
Titel: Ueber eine elementare Frage der Mannigfaltigketislehre. Autor: Cantor, Georg. PURL: https://resolver.sub.uni-goettingen.de/purl?37721857X_0001 ...Missing: 1891 | Show results with:1891
[11]
[PDF] Diagonals without tears - Harald Hanche-Olsen
Apr 1, 2025 · Briefly exploring a minor innovation in the pedagogy of mathematical analysis. Diagonal arguments play a minor but important role in many proofs.
[12]
[PDF] 1·Eigenvalues - Princeton University
the 1830s; Sylvester and Cayley's diagonalization of symmetric matrices in the 1850s (the origins of this idea go back to Cauchy, Jacobi, Lagrange, ... Jordan ...<|separator|>
[13]
[PDF] On the Early History of the Singular Value Decomposition
his famous algorithm for diagonalizing a symmetric matrix, andin a posthumous paper [31,. 1857] he obtained the LU decomposition by decomposing abilinear form ...
[14]
[PDF] Jordan's Normal Form - People @EECS
Dec 7, 2000 · The second form to which every square matrix B can be reduced by complex similarity is a diagonal sum of triangular matrices of which each has ...Missing: 1775 1870
[15]
Cantors 1891 Diagonal Proof - English Translation - Logic
Bd. I, S. pp 75-78 (1891). This is the basis for the Diagonal proof and for the Power Set Theorem. The original German text of Cantor's proof is also included ...Missing: citation | Show results with:citation
[16]
Hilbert's Program - Stanford Encyclopedia of Philosophy
Jul 31, 2003 · This proposal incorporated Hilbert's ideas from 1904 regarding direct consistency proofs, his conception of axiomatic systems, and also the ...
[17]
Gödel's Incompleteness Theorems
Nov 11, 2013 · Gödel's two incompleteness theorems are among the most important results in modern logic, and have deep implications for various issues.
[18]
[PDF] An Unsolvable Problem of Elementary Number Theory Alonzo ...
Mar 3, 2008 · Alonzo Church. American Journal of Mathematics, Vol. 58, No. 2. (Apr., 1936), pp. 345-363. Stable URL:.
[19]
[PDF] ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ...
By A. M. TURING. [Received 28 May, 1936.—Read 12 November, 1936.] The "computable" numbers may be described briefly ...
[20]
Eigenvalues and Eigenvectors
An eigenvector v satisfies Av = λv, where λ is an eigenvalue. 'Eigen' means 'self' or 'own', and 'eigen' means 'characteristic'.
[21]
4.1 An introduction to eigenvalues and eigenvectors
An eigenvector of a matrix is a nonzero vector that, when multiplied by the matrix, results in a scalar multiplication by an associated eigenvalue.
[22]
Differential Equations - Review : Eigenvalues & Eigenvectors
Nov 16, 2022 · In this section we will introduce the concept of eigenvalues and eigenvectors of a matrix. We define the characteristic polynomial and show ...
[23]
[PDF] algebraic and geometric multiplicities of eigenvalues, generalized ...
Algebraic multiplicity is the maximal number of appearances of (x-λ) in det(A-xI). Geometric multiplicity is the dimension of the eigenspace of λ.
[24]
[PDF] Computing Eigenvalues and their algebraic and geometric ...
The geometric multiplicity of eigenvalue λ is the dimension of the λ-eigenspace—equivalently, the dimension of ker(A − λIn).
[25]
Eigenvalues of 2 × 2 Matrices - Ximera - The Ohio State University
Thus, for matrices, the trace is the sum of the eigenvalues and the determinant is the product of the eigenvalues. In Chapter ??, Theorems ??(b) and ?? we show ...Missing: properties | Show results with:properties
[26]
[PDF] Eigenvalues and Eigenvectors - ScholarWorks@GVSU
The Fundamental Theorem of Algebra shows us that if a real matrix has complex eigenvalues, then those eigenvalues will appear in conjugate pairs, i.e., if λ1 = ...
[27]
[PDF] Notes on Eigenvalues and Eigenvectors - UT Computer Science
Oct 31, 2014 · Exercise 8. The eigenvalues of a diagonal matrix equal the values on its diagonal. The eigenvalues of a triangular matrix equal the values on ...
[28]
[PDF] Rotations and complex eigenvalues Math 130 Linear Algebra
Rotations have complex eigenvalues, not real ones, and are calculated using complex numbers. The complex eigenvalues are cosθ ± isinθ = e±iθ.
[29]
[PDF] 20. Diagonalisation Definition 20.1. Let A and B be two square n × n ...
Multiplying both sides by P on the left, we get. PD = AP. Finally multiplying both sides on the right by P-1 we get. A = PDP-1. D. Let's illustrate ...
[30]
[PDF] Intro to Differential Equations: A Subtle Subject
Diagonalization Criterion: Let A be an n × n matrix. Then: A is diagonalizable ⇐⇒ A has n linearly independent eigenvectors. ⇐⇒ Every eigenvalue λ of A has.
[31]
EIG-0050: Diagonalizable Matrices and Multiplicity - Ximera
Recall that a diagonal matrix is a matrix containing a zero in every entry except those on the main diagonal. More precisely, if is the entry of a diagonal ...
[32]
[PDF] the minimal polynomial and some applications - Penn Math
Theorem 4.11. Let A: V → V be a linear operator. Then A is diagonalizable if and only if its minimal polynomial in F[T] splits in F[T] and has distinct roots.
[33]
[PDF] Recitation 8. November 5 - MIT
The matrix A is diagonalizable if and only if the geometric multiplicity of each eigenvalue of A is equal to the algebraic multiplicity of that eigenvalue. The ...
[34]
[PDF] Symmetric Matrices and the Spectral Theorem - Purdue Math
May 4, 2025 · ... symmetric matrices is that a symmetric matrix with real entries is always diagonalizable and all the eigenvalues and eigenvectors are real.
[35]
[PDF] SPECTRAL THEOREM Orthogonal Diagonalizable A diagonal ...
(Spectral theorem) A ∈ Rn×n is orthogonally diagonalizable if and only if it is symmetric. An important consequence of this is that a symmetric n×n matrix has ( ...
[36]
Traité des substitutions et des équations algébriques - Internet Archive
Dec 3, 2008 · Traité des substitutions et des équations algébriques. by: Jordan, Camille, 1838-1922. Publication date: 1870. Topics: Galois theory, Groups ...Missing: canonical | Show results with:canonical
[37]
Matrix Analysis - Cambridge University Press & Assessment
Chapter 1 - Eigenvalues, eigenvectors, and similarity. pp 33-64 · You have access Access · PDF · Export citation.
[38]
(PDF) A Translation of G. Cantor's “Ueber eine elementare Frage ...
Aug 23, 2019 · We examine Cantor's Diagonal Argument (CDA). If the same basic assumptions and theorems found in many accounts of set theory are applied with a ...
[39]
[PDF] Infinite continued fractions - People
In the very last section of Book I, Section 7.10, we look at continued fractions ... Using a Cantor diagonal argument as in the proof of Theorem 3.35, prove that ...
[40]
https://www.pnas.org/doi/10.1073/pnas.26.7.402
[41]
Supplement: The Diagonalization Lemma
The proof of the Diagonalization Lemma centers on the operation of substitution (of a numeral for a variable in a formula).
[42]
Über formal unentscheidbare Sätze der Principia Mathematica und ...
Gödel, K. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatsh. f. Mathematik und Physik 38, 173–198 (1931). ... citation.
[43]
[PDF] 23.1 Gödel Numberings and Diagonalization
Apr 14, 2009 · Note that the diagonal lemma holds for Peano Arithmetic, as diag is representable in any theory that can represent the computable functions ...
[44]
Self-Reference and Paradox - Stanford Encyclopedia of Philosophy
Jul 15, 2008 · Self-reference is used to denote a statement that refers to itself or its own referent. The most famous example of a self-referential sentence is the liar ...
[45]
[PDF] Lecture 10: Undecidability, Unrecognizability, and Reductions
Theorem: HALT. TM is undecidable. The Halting Problem [Turing]. Proof: Assume (for a contradiction) there is a TM H that decides HALT. TM. Idea: Use H to ...
[46]
[PDF] MITOCW | 8. Undecidability
We're going to give a proof by contradiction using diagonalization. And we're going to assume some Turing machine, H, decides A,TM. And we're going to get a.
[47]
https://www.cs.cmu.edu/~arielpro/15251f15/recitation/recitation03-sols.pdf
[48]
[PDF] 18.102 S2021 Lecture 22. The Spectral Theorem for a Compact Self ...
May 11, 2021 · We discussed previously that for a self-adjoint operator, the spectrum is contained within a line segment on the real line, and in the finite- ...
[49]
[PDF] spectral theory for compact self-adjoint operators
For compact self-adjoint operators, eigenvalues are real, and the span of eigenspaces is dense in H, forming an orthonormal basis. If 0 is an eigenvalue, its ...
[50]
[PDF] Chapter 9: The Spectrum of Bounded Linear Operators
A bounded linear operator on an infinite-dimensional & ilbert space need not have any eigenvalues at all, even if it is self-adjoint (seeCX xample ./} below) .
[51]
[PDF] Mathematical Quantum Mechanics with Applications
The first part focuses on the spectral theorem for self-adjoint op- erators and discusses several of its applications.
[52]
[PDF] Eigenfunctions of the Laplacian of Riemannian manifolds Updated
Aug 15, 2017 · These lecture notes are an expanded version of the author's CBMS ten Lectures at the University of Kentucky in June 20-24, 2011.
[53]
[PDF] C ontents Introduction vii 1 The Laplacian on a Riemannian ...
... L2 Spaces ofFunctions and Forms . . . . . . . . . . . . . 14. 1.2.3 The ... diagonalization of the Laplacian : A λ. 1 λ. 2... . Remar s : ( 1 ) We can ...