Proof of The Operator Norm of a Symmetric Matrix: Quadratic Forms, Eigenvalues and the Semidefinite Ordering

Each result cited is universally quantified over the data in its own statement.

We work in Routine Facts Used Without Citation: Arithmetic, Maps, Predicativity and Indices. $\mathbb{R}$ is an ordered field by The Real Numbers Form an Ordered Field in Which Every Nonempty Set Bounded Above Has a Supremum §ordered-field, so the results on ordered fields cited below apply to it. Every $C\in\mathcal{S}(n)$ is symmetric, $C^{\top}=C$, by Symmetric Real Matrices and the Set $\mathcal{S}(n)$ §set and Symmetric Real Matrices and the Set $\mathcal{S}(n)$ §symmetric. For every point $w$ of $\mathbb{R}^{n}$, $\lVert w\rVert\ge0$ and $\lVert w\rVert^{2}=w\cdot w$ by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §square. For every real matrix $C$, $\lVert C\rVert\in\mathbb{R}$ by The Operator Norm of a Real Matrix §values, and $\lVert C\rVert\ge0$ by Rules for the Operator Norm: Bound, Least Constant, Definiteness, Homogeneity, Triangle Inequality and Products §nonnegative. Matrix-vector products obey Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, cited as MV below.

Preliminaries. (P) If $u\in\mathbb{R}^{n}$ with $\lVert u\rVert\le1$ and $c\in\mathbb{R}$ with $c\ge0$, then $c\,\lVert u\rVert^{2}\le c$: by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §nonnegative-scaling, with $\lVert u\rVert$ for its $z$, $\lVert u\rVert^{2}=\lVert u\rVert\,\lVert u\rVert\le\lVert u\rVert\le1$, and with $c$ for its $z$, $c\,\lVert u\rVert^{2}\le c$.

Let $U_{n}=\{u\in\mathbb{R}^{n}:\lVert u\rVert\le1\}$, the closed unit ball of The Set of Lengths ‖Ax‖ over the Unit Ball Has a Supremum, and the Supremum Map Exists with $n$ for its $m$ and its $n$; by The Set of Lengths ‖Ax‖ over the Unit Ball Has a Supremum, and the Supremum Map Exists §membership, $u\in U_{n}$ if and only if $u\in\mathbb{R}^{n}$ and $\lVert u\rVert\le1$. Let $R_{A}=\{|u\cdot(Au)|:u\in U_{n}\}$. Take no variables $x_{i}$ and the guard $A\in\mathcal{S}(n)$, in which $A$ and $\mathcal{S}(n)$ are parameters; note that $\mathcal{S}(n)\subseteq\mathcal{M}_{n}(\mathbb{R})$, by Symmetric Real Matrices and the Set $\mathcal{S}(n)$ §set. Under the guard $A\in\mathcal{S}(n)\wedge u\in U_{n}$, for the variable $u$, the term $|u\cdot(Au)|$ is of type $\mathbb{R}$: $u$ and $A$ are terms of type $\mathbb{R}^{n}$ and $\mathcal{M}_{n}(\mathbb{R})$ (Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them §variable, Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them §parameter), and pairs of terms and values of maps at terms are terms (Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them §pair, Typed Terms under a Predicative Guard: Variables, Parameters, Values of Maps and Ordered Pairs, and Predicative Equations and Memberships between Them §value), here of the maps of The Matrix Product, Matrix-Vector Product, Transpose, Trace, Identity Matrix and Standard Basis Vectors Exist and Are Unique §matrix-vector, The Summation Map on Real-Valued Maps over a Finite Set, and the Dot Product, Euclidean Norm and Euclidean Distance as Maps §dot-product and Absolute Value and Squaring as Maps on the Reals, and Entrywise Absolute Values and Squares of a Real Matrix §absolute-value. So, by Images of Typed Terms: the Set of Values $\{t:u\in D\}$ Is a Set, Finite when $D$ Is Finite, and a Typed Term §set and Images of Typed Terms: the Set of Values $\{t:u\in D\}$ Is a Set, Finite when $D$ Is Finite, and a Typed Term §members, with $u$ for its $u$, $U_{n}$ for its $D$ and $\mathbb{R}$ for its $B$, $R_{A}$ is a set and a subset of $\mathbb{R}$, and for every set $s$: $s\in R_{A}$ if and only if $s=|u\cdot(Au)|$ for some $u\in U_{n}$. By this and the membership of $U_{n}$ above, the elements of $R_{A}$ are exactly the numbers $|u\cdot(Au)|$ with $u\in\mathbb{R}^{n}$ and $\lVert u\rVert\le1$; so $R_{A}$ coincides with the set $\{|u\cdot(Au)|:u\in\mathbb{R}^{n},\ \lVert u\rVert\le1\}$ of the clause rayleigh, by Axiom of Extensionality for Classes.

Clause quadratic-bound. Let $x\in\mathbb{R}^{n}$. By The Cauchy-Schwarz Inequality on $\mathbb{R}^n$ §cauchy-schwarz, then Rules for the Operator Norm: Bound, Least Constant, Definiteness, Homogeneity, Triangle Inequality and Products §bound with Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §nonnegative-scaling ($\lVert x\rVert\ge0$ for its $z$),

$$|x\cdot(Ax)|\le\lVert x\rVert\,\lVert Ax\rVert\le\lVert x\rVert\,\lVert A\rVert\,\lVert x\rVert=\lVert A\rVert\,\lVert x\rVert^{2}.$$

Clause identity. Let $t\in\mathbb{R}$ and $z\in\mathbb{R}^{n}$. $I_{n}\in\mathcal{S}(n)$, and hence $tI_{n}\in\mathcal{S}(n)$, by Rules for Symmetric and Positive Semidefinite Matrices: Closure, Self-Adjointness, Polarization, Congruence and Cones §closure. By MV, $(tI_{n})z=t(I_{n}z)=tz$; by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §second, $z\cdot(tz)=t\,(z\cdot z)=t\,\lVert z\rVert^{2}$. By The Operator Norm of Entries, Transposes, Multiples of the Identity, Orthogonal Factors and Diagonal Matrices §identity, with $n$ for its $m$ and its $n$, $\lVert tI_{n}\rVert=|t|$.

Clause eigenvalues. Let $Q\in\mathrm{O}(n)$ and $d\in\mathbb{R}^{n}$ with $A=(Q\operatorname{diag}(d))Q^{\top}$; the products exist by The Matrix Product, Matrix-Vector Product, Transpose, Trace, Identity Matrix and Standard Basis Vectors Exist and Are Unique §product. By Rules for Orthogonal Matrices: Inverse, Products, Isometry, Columns, Determinant, Orthonormal Extension and Expansion §inverse, $Q^{\top}\in\mathrm{O}(n)$. By The Operator Norm of Entries, Transposes, Multiples of the Identity, Orthogonal Factors and Diagonal Matrices §orthogonal with $m=n$, first with $Q\operatorname{diag}(d)$ for its $A$ and $Q^{\top}$ for its $R$, then with $\operatorname{diag}(d)$ for its $A$ and $Q$ for its $Q$, and by The Operator Norm of Entries, Transposes, Multiples of the Identity, Orthogonal Factors and Diagonal Matrices §diagonal,

$$\lVert A\rVert=\lVert(Q\operatorname{diag}(d))Q^{\top}\rVert=\lVert Q\operatorname{diag}(d)\rVert=\lVert\operatorname{diag}(d)\rVert=\max_{k\in[n]}|d_{k}|.$$

Clause rayleigh. Upper bound: for $u\in U_{n}$, the clause quadratic-bound and (P) with $\lVert A\rVert$ for $c$ give $|u\cdot(Au)|\le\lVert A\rVert\,\lVert u\rVert^{2}\le\lVert A\rVert$; so $\lVert A\rVert$ is an upper bound of $R_{A}$ by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §bounds.

Attainment: by The Spectral Theorem for Real Symmetric Matrices §diagonalization there are $Q\in\mathrm{O}(n)$ and $d\in\mathbb{R}^{n}$ with $A=(Q\operatorname{diag}(d))Q^{\top}$. By the clause eigenvalues, $\lVert A\rVert=\max_{k\in[n]}|d_{k}|$, an element of $\{|d_{k}|:k\in[n]\}$ by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §least. Let $k_{0}\in[n]$ with $\lVert A\rVert=|d_{k_{0}}|$, and let $v=Qe_{k_{0}}$, with $e_{k_{0}}$ the standard basis vector (it exists by The Matrix Product, Matrix-Vector Product, Transpose, Trace, Identity Matrix and Standard Basis Vectors Exist and Are Unique §basis). By The Spectral Theorem for Real Symmetric Matrices §eigenvectors, $v$ is an eigenvector of $A$ with eigenvalue $d_{k_{0}}$, so $Av=d_{k_{0}}v$ by Real Eigenvalues and Eigenvectors of a Real Square Matrix §eigenvector. By Rules for Orthogonal Matrices: Inverse, Products, Isometry, Columns, Determinant, Orthonormal Extension and Expansion §isometry and Standard Basis Vectors of ℝ^q: Coordinates, Orthonormality and Unit Length §unit, $\lVert v\rVert=\lVert Qe_{k_{0}}\rVert=\lVert e_{k_{0}}\rVert=1$, so $v\in U_{n}$ and $v\cdot v=\lVert v\rVert^{2}=1$. By The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §second,

$$|v\cdot(Av)|=|v\cdot(d_{k_{0}}v)|=|d_{k_{0}}\,(v\cdot v)|=|d_{k_{0}}|=\lVert A\rVert,$$

so $\lVert A\rVert\in R_{A}$.

Hence $\lVert A\rVert$ is an upper bound of $R_{A}$ in $\mathbb{R}$, and $\lVert A\rVert\le b$ for every upper bound $b$ of $R_{A}$, as $\lVert A\rVert\in R_{A}$. So $\lVert A\rVert$ is the least element of the set of upper bounds of $R_{A}$ (Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §bounds and Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §least), that is, the supremum of $R_{A}$, which is unique, by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §supremum.

Clause rayleigh-bound. Let $b\in\mathbb{R}$ with $|u\cdot(Au)|\le b$ for every $u\in U_{n}$. Then $b$ is an upper bound of $R_{A}$ by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §bounds, and $\lVert A\rVert$, the supremum of $R_{A}$ by the clause rayleigh, is the least element of the set of upper bounds of $R_{A}$ by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §supremum; so $\lVert A\rVert\le b$ by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §least.

Clause ordering. Let $\lambda\in\mathbb{R}$ with $0\le\lambda$. The matrices $\lambda I_{n}$ and $(-\lambda)I_{n}$ lie in $\mathcal{S}(n)$ by the clause identity, and for every $w\in\mathbb{R}^{n}$, by the clause identity and Rules of Arithmetic and Order in an Ordered Field §signs,

$$w\cdot((\lambda I_{n})w)=\lambda\,\lVert w\rVert^{2},\qquad w\cdot(((-\lambda)I_{n})w)=(-\lambda)\lVert w\rVert^{2}=-(\lambda\,\lVert w\rVert^{2}).$$

Suppose $\lVert A\rVert\le\lambda$, and let $w\in\mathbb{R}^{n}$. By the clause quadratic-bound and Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §nonnegative-scaling ($\lVert w\rVert^{2}\ge0$ for its $z$), $|w\cdot(Aw)|\le\lVert A\rVert\,\lVert w\rVert^{2}\le\lambda\,\lVert w\rVert^{2}$, so $-(\lambda\lVert w\rVert^{2})\le w\cdot(Aw)\le\lambda\lVert w\rVert^{2}$ by Rules of Arithmetic and Order in an Ordered Field §absolute-value. By The Positive Semidefinite Ordering on Symmetric Matrices §order, $(-\lambda)I_{n}\preceq A$ and $A\preceq\lambda I_{n}$.

Conversely, suppose $(-\lambda)I_{n}\preceq A$ and $A\preceq\lambda I_{n}$, and let $u\in U_{n}$. By The Positive Semidefinite Ordering on Symmetric Matrices §order and the display above, $-(\lambda\lVert u\rVert^{2})\le u\cdot(Au)\le\lambda\lVert u\rVert^{2}$, so $|u\cdot(Au)|\le\lambda\lVert u\rVert^{2}$ by Rules of Arithmetic and Order in an Ordered Field §absolute-value, and $\lambda\lVert u\rVert^{2}\le\lambda$ by (P). By the clause rayleigh-bound with $\lambda$ for $b$, $\lVert A\rVert\le\lambda$.

Clause ordering-norm. The number $\lambda=\lVert A\rVert\in\mathbb{R}$ satisfies $0\le\lambda$ and $\lVert A\rVert\le\lambda$, so the clause ordering gives $(-\lVert A\rVert)I_{n}\preceq A\preceq\lVert A\rVert I_{n}$.

Clause square. Let $z\in\mathbb{R}^{n}$. The product $A^{2}=AA\in\mathcal{M}_{n}(\mathbb{R})$ is the value of the map of The Matrix Product, Matrix-Vector Product, Transpose, Trace, Identity Matrix and Standard Basis Vectors Exist and Are Unique §product, by Product of Real Matrices §product. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §transpose, $(AA)^{\top}=A^{\top}A^{\top}=AA$, so $A^{2}\in\mathcal{S}(n)$ by Symmetric Real Matrices and the Set $\mathcal{S}(n)$ §set. By Rules for Symmetric and Positive Semidefinite Matrices: Closure, Self-Adjointness, Polarization, Congruence and Cones §self-adjoint, with $z$ for its $x$ and $Az$ for its $y$, and by MV,

$$\lVert Az\rVert^{2}=(Az)\cdot(Az)=z\cdot(A(Az))=z\cdot((AA)z)=z\cdot(A^{2}z).$$

Clause square-norm. By Rules for the Operator Norm: Bound, Least Constant, Definiteness, Homogeneity, Triangle Inequality and Products §product, $\lVert A^{2}\rVert\le\lVert A\rVert\,\lVert A\rVert=\lVert A\rVert^{2}$. Conversely, as $\lVert A^{2}\rVert\ge0$, Existence and Uniqueness of Nonnegative k-th Roots of Nonnegative Real Numbers §root with $k=2$ gives $s\in\mathbb{R}$ with $s\ge0$ and $s^{2}=\lVert A^{2}\rVert$. Let $x\in\mathbb{R}^{n}$. By the clause square with $x$ for $z$, by Rules of Arithmetic and Order in an Ordered Field §absolute-value, and by the clause quadratic-bound applied to $A^{2}\in\mathcal{S}(n)$ in place of $A$, which it may be since that clause is proved above for every element of $\mathcal{S}(n)$,

$$\lVert Ax\rVert^{2}=x\cdot(A^{2}x)\le|x\cdot(A^{2}x)|\le\lVert A^{2}\rVert\,\lVert x\rVert^{2}=s^{2}\lVert x\rVert^{2}=(s\,\lVert x\rVert)^{2}.$$

As $\lVert Ax\rVert\ge0$ and $s\,\lVert x\rVert\ge0$ (Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §positive-product), Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §monotone-iff, with $2$ for its $n$, gives $\lVert Ax\rVert\le s\,\lVert x\rVert$. By Rules for the Operator Norm: Bound, Least Constant, Definiteness, Homogeneity, Triangle Inequality and Products §least with $s$ for its $c$, $\lVert A\rVert\le s$. As $\lVert A\rVert\ge0$ and $s\ge0$, Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §monotone-iff, with $2$ for its $n$, gives $\lVert A\rVert^{2}\le s^{2}=\lVert A^{2}\rVert$. Hence $\lVert A^{2}\rVert=\lVert A\rVert^{2}$.

Clause quadratic-comparison. Let $x,y\in\mathbb{R}^{n}$. By MV, $A(x+y)=Ax+Ay$. By The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §second and then The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §first,

$$(x-y)\cdot(A(x+y))=(x-y)\cdot(Ax)+(x-y)\cdot(Ay)=x\cdot(Ax)-y\cdot(Ax)+x\cdot(Ay)-y\cdot(Ay).$$

By The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §symmetric and Rules for Symmetric and Positive Semidefinite Matrices: Closure, Self-Adjointness, Polarization, Congruence and Cones §self-adjoint, $y\cdot(Ax)=(Ax)\cdot y=x\cdot(Ay)$, so $(x-y)\cdot(A(x+y))=x\cdot(Ax)-y\cdot(Ay)$. By The Cauchy-Schwarz Inequality on $\mathbb{R}^n$ §cauchy-schwarz, then Rules for the Operator Norm: Bound, Least Constant, Definiteness, Homogeneity, Triangle Inequality and Products §bound with Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §nonnegative-scaling ($\lVert x-y\rVert\ge0$ for its $z$),

$$|x\cdot(Ax)-y\cdot(Ay)|\le\lVert x-y\rVert\,\lVert A(x+y)\rVert\le\lVert A\rVert\,\lVert x-y\rVert\,\lVert x+y\rVert.$$

Clause monotone. Let $B\in\mathcal{S}(n)$, and suppose $0\preceq A$ and $A\preceq B$. By The Positive Semidefinite Ordering is a Partial Order Compatible with the Linear Structure §zero, $A$ is positive semidefinite, so $u\cdot(Au)\ge0$ and $|u\cdot(Au)|=u\cdot(Au)$ for every $u\in\mathbb{R}^{n}$, by Positive Semidefinite and Positive Definite Real Matrices §psd and Absolute Value in an Ordered Field §absolute-value. Let $u\in U_{n}$. By The Positive Semidefinite Ordering on Symmetric Matrices §order, Rules of Arithmetic and Order in an Ordered Field §absolute-value, the clause quadratic-bound applied to $B\in\mathcal{S}(n)$ in place of $A$ (that clause being proved for every element of $\mathcal{S}(n)$), and (P) with $\lVert B\rVert$ for $c$,

$$|u\cdot(Au)|=u\cdot(Au)\le u\cdot(Bu)\le|u\cdot(Bu)|\le\lVert B\rVert\,\lVert u\rVert^{2}\le\lVert B\rVert.$$

By the clause rayleigh-bound with $\lVert B\rVert$ for $b$, $\lVert A\rVert\le\lVert B\rVert$.