Proof of Vector, Entry and Comparison Bounds for the Norm of a Symmetric Real Matrix

Throughout we use the notation of the statement. Since $X\in\mathcal{S}(n)$ we have $X^{\top}=X$, and therefore

because claim 5 of Elementary Properties of the Transpose of a Real Matrix gives $a\cdot(Xb)=(X^{\top}a)\cdot b=(Xa)\cdot b$, and $(Xa)\cdot b=b\cdot(Xa)$ by claim 1 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$. We also use that $\lVert e_{i}\rVert=1$ for every $i\in[n]$, as recorded in Real Matrices, Symmetric Matrices and the Semidefinite Ordering: Standing Notation §basis.

Claim 1. By claim 4 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum,

Fix $k\in[n]$. The factor $(e_{i})_{k}$ does not depend on $l$, so claim 3 of Properties of Finite Sums gives

By Orthonormal Families, Standard Basis Vectors, and Plane Rotations of Euclidean Space the $l$th coordinate of $e_{j}$ is $1$ for $l=j$ and $0$ otherwise, so every summand of the last sum with $l\ne j$ vanishes and claim 7 of Properties of Finite Sums gives $\sum_{l=1}^{n}A_{kl}(e_{j})_{l}=A_{kj}$. Hence

and a second application of claim 7 of Properties of Finite Sums, now with the $k$th coordinate of $e_{i}$, gives $e_{i}\cdot(Ae_{j})=A_{ij}$.

Claim 2. By claim 4 of Elementary Properties of the Transpose of a Real Matrix and $X^{\top}=X$ we get $(XX)^{\top}=X^{\top}X^{\top}=XX$, so $X^{2}=XX$ is symmetric and hence lies in $\mathcal{S}(n)$ by The Set of Symmetric Real Matrices. Next, by claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$,

Applying claim 5 of Elementary Properties of the Transpose of a Real Matrix with the vector $Xz$ in the first slot and $z$ in the second gives $(Xz)\cdot(Xz)=\bigl(X^{\top}(Xz)\bigr)\cdot z=\bigl(X(Xz)\bigr)\cdot z$, and $X(Xz)=(XX)z=X^{2}z$ by claim 2 of Linearity, Compatibility with the Matrix Product, and a Norm Bound for the Matrix-Vector Product. Finally $(X^{2}z)\cdot z=z\cdot(X^{2}z)$ by claim 1 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$.

Claim 3. Suppose first that $\lVert X\rVert=0$. Then $X=0_{n}$ by claim 4 of Properties of the Norm of a Symmetric Real Matrix, so by claim 4 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum every $w\in\mathbb{R}^{n}$ satisfies $w\cdot(Xz)=\sum_{k=1}^{n}\sum_{l=1}^{n}0\cdot w_{k}z_{l}=0$, the summands all being $0$; taking $w=Xz$ and using claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ gives $\lVert Xz\rVert^{2}=0$, hence $\lVert Xz\rVert=0$ by claim 3 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field, and the asserted inequality holds because $\lVert X\rVert\,\lVert z\rVert=0$.

Now suppose $0<\lVert X\rVert$ and put $t=\lVert X\rVert^{-1}$, which exists and is positive by claim 7 of Elementary Order Arithmetic in an Ordered Field. Put $w=t\,(Xz)$. Using $X(w\pm z)=Xw\pm Xz$, which is claim 3 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, and expanding both dot products by claims 2, 3 and 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$, we obtain

the last equality by the symmetry identity recorded above. By claim 2 of Properties of the Norm of a Symmetric Real Matrix together with claim 3 of Properties of the Absolute Value in an Ordered Field, the first term on the left is at most $\lVert X\rVert\,\lVert w+z\rVert^{2}$ and the second is at least $-\lVert X\rVert\,\lVert w-z\rVert^{2}$, so

the last identity following by expanding $\lVert w\pm z\rVert^{2}=(w\pm z)\cdot(w\pm z)$ with claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ and claims 1, 2, 3 and 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$. Now $w\cdot(Xz)=t\,(Xz)\cdot(Xz)=t\,\lVert Xz\rVert^{2}$ by claim 4 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ and claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$, and $\lVert w\rVert^{2}=t^{2}\lVert Xz\rVert^{2}$ by claim 5 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ and $|t|=t$. Since $\lVert X\rVert\,t^{2}=t$, the displayed inequality becomes

so $2t\,\lVert Xz\rVert^{2}\le2\lVert X\rVert\,\lVert z\rVert^{2}$. Multiplying by the positive number $\tfrac{1}{2}\lVert X\rVert$ and using $\lVert X\rVert\,t=1$ gives

Both $\lVert Xz\rVert$ and $\lVert X\rVert\,\lVert z\rVert$ are nonnegative, by claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ and claim 1 of Properties of the Norm of a Symmetric Real Matrix together with claim 5 of Elementary Order Arithmetic in an Ordered Field, so claim 2 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field yields $\lVert Xz\rVert\le\lVert X\rVert\,\lVert z\rVert$.

Claim 4. By claim 1, $X_{ij}=e_{i}\cdot(Xe_{j})$. By Cauchy-Schwarz Inequality for the Euclidean Dot Product and claim 3,

since $\lVert e_{i}\rVert=\lVert e_{j}\rVert=1$ as recorded above.

Claim 5. Let $\xi\in\mathbb{R}^{n}$ with $\lVert\xi\rVert\le1$. By claim 4 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, $\xi\cdot(X\xi)=\sum_{i=1}^{n}\sum_{j=1}^{n}X_{ij}\xi_{i}\xi_{j}$. Applying claim 2 of Comparison and Absolute Value Bounds for Finite Sums of Real Numbers to the outer sum, then claim 1 of that lemma together with claim 2 of it applied to each inner sum, and finally claim 4 of Properties of the Absolute Value in an Ordered Field, we obtain

By claim 4 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$ we have $|\xi_{i}|\le\lVert\xi\rVert\le1$ for every $i$, and all the factors involved are nonnegative, so $|X_{ij}|\,|\xi_{i}|\,|\xi_{j}|\le|X_{ij}|$ for all $i,j$; claim 1 of Comparison and Absolute Value Bounds for Finite Sums of Real Numbers, applied twice, then gives

Thus the right-hand side is an upper bound for the set whose least upper bound is $\lVert X\rVert$ by Norm of a Symmetric Real Matrix, and therefore $\lVert X\rVert\le\sum_{i=1}^{n}\sum_{j=1}^{n}|X_{ij}|$.

Claim 6. By Identity Matrix and Scalar Multiple of a Real Matrix the entry of $aI_{n}$ in row $k$ and column $l$ is $a$ if $k=l$ and $0$ otherwise; interchanging $k$ and $l$ leaves this unchanged, so $aI_{n}$ is symmetric and lies in $\mathcal{S}(n)$. For $\xi\in\mathbb{R}^{n}$, claim 1 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum gives $(aI_{n})\xi=a(I_{n}\xi)=a\xi$ by claim 2 there, so by claim 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ and claim 1 of Elementary Properties of the Euclidean Norm on $\mathbb{R}^n$,

This is the second assertion of the claim. If $\lVert\xi\rVert\le1$ then $\lVert\xi\rVert^{2}\le1$ by claim 2 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field, so $|a\lVert\xi\rVert^{2}|=|a|\,\lVert\xi\rVert^{2}\le|a|$ by claim 4 of Properties of the Absolute Value in an Ordered Field; hence $|a|$ is an upper bound for the set in Norm of a Symmetric Real Matrix and $\lVert aI_{n}\rVert\le|a|$. Conversely $1\le n$, so $e_{1}$ is defined and satisfies $\lVert e_{1}\rVert=1$; the number $|e_{1}\cdot((aI_{n})e_{1})|=|a|\cdot1=|a|$ therefore belongs to that set, whence $|a|\le\lVert aI_{n}\rVert$. The two inequalities give $\lVert aI_{n}\rVert=|a|$.

Claim 7. Using claim 3 of Linearity of the Matrix-Vector Product and the Quadratic Form as a Double Sum, claims 2, 3 and 5 of Bilinearity and Symmetry of the Dot Product on $\mathbb{R}^n$ and the symmetry identity recorded at the start,

Hence, by Cauchy-Schwarz Inequality for the Euclidean Dot Product and claim 3,