Proof of A Maximiser of the Quadratic Form of a Symmetric Matrix on Unit Vectors Orthogonal to Given Eigenvectors Is an Eigenvector

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. Let $d_{E}$ be the Euclidean distance on $\mathbb{R}^{n}$, a metric by $\mathbb{R}^n$ with the Euclidean Distance Is a Complete Metric Space with Coordinatewise Convergence §metric, and let $\mathcal{T}_{d_{E}}$ be the topology of Metric Spaces: Balls, the Metric Topology, and the Real and Complex Numbers as Metric Spaces §topology, so that $(\mathbb{R}^{n},\mathcal{T}_{d_{E}})$ is a topological space whose members are the subsets of $\mathbb{R}^{n}$ that are open in $(\mathbb{R}^{n},d_{E})$. For $x\in\mathbb{R}^{n}$ write $q(x)=x\cdot(Ax)$, a real number by The Dot Product on $\mathbb{R}^n$ §dot-product. No choice principle is used: every existential statement below is instantiated once, for one object.

Facts used throughout.

(F1) For $x,y\in\mathbb{R}^{n}$, $x\cdot(Ay)=y\cdot(Ax)$: indeed $x\cdot(Ay)=(Ay)\cdot x$ by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §symmetric, and $(Ay)\cdot x=y\cdot(Ax)$ by Rules for Symmetric and Positive Semidefinite Matrices: Closure, Self-Adjointness, Polarization, Congruence and Cones §self-adjoint, as $A\in\mathcal{S}(n)$.

(F2) For $i\in[k]$, $\lVert u_{i}\rVert=1$: by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §square, $\lVert u_{i}\rVert$ is the only nonnegative real number whose square is $u_{i}\cdot u_{i}=1$, and $1\ge0$ (as $0<1$ by Rules of Arithmetic and Order in an Ordered Field §squares) with $1^{2}=1$ by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product. For $x\in K$, $x\cdot x=\lVert x\rVert^{2}=1$ by the same clause.

(F3) For $a\in\mathbb{R}$, $a^{2}=a\,a$, by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §exponents and Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product with $2=1+1$; $a^{2}\ge0$ by Rules of Arithmetic and Order in an Ordered Field §squares. For $a,b\in\mathbb{R}$ with $a\ge0$, $b\ge0$ and $a^{2}\le b^{2}$, we have $a\le b$, by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §monotone-iff with exponent $2$.

Clause maximiser.

Step 1: $K$ is nonempty. By Rules for Orthogonal Matrices: Inverse, Products, Isometry, Columns, Determinant, Orthonormal Extension and Expansion §extension, applied to $k<n$ and to the map $u$, there is $v_{0}\in\mathbb{R}^{n}$ with $\lVert v_{0}\rVert=1$ and $v_{0}\cdot u_{i}=0$ for every $i\in[k]$, so $v_{0}\in K$.

Step 2: $K$ is closed in $(\mathbb{R}^{n},\mathcal{T}_{d_{E}})$. Let $y\in\mathbb{R}^{n}\setminus K$. Then $\lVert y\rVert\neq1$, or $y\cdot u_{i}\neq0$ for some $i\in[k]$. For $z\in\mathbb{R}^{n}$ we have $d_{E}(y,z)=d_{E}(z,y)=\lVert z-y\rVert$ by Metric Space §symmetric and Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §distance, and $z$ lies in the open ball $B_{d_{E}}(y,\varepsilon)$ of a radius $\varepsilon>0$ if and only if $d_{E}(y,z)<\varepsilon$, by Open Ball in a Metric Space §membership.

If $\lVert y\rVert\neq1$, let $\varepsilon=|\lVert y\rVert-1|$, which is $>0$ by Rules of Arithmetic and Order in an Ordered Field §absolute-value. For $z\in B_{d_{E}}(y,\varepsilon)$, Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §reverse-triangle gives $|\lVert z\rVert-\lVert y\rVert|\le\lVert z-y\rVert<\varepsilon$; if $\lVert z\rVert=1$ this would read $|1-\lVert y\rVert|<|\lVert y\rVert-1|=|1-\lVert y\rVert|$ (the last equality by Rules of Arithmetic and Order in an Ordered Field §absolute-value), which is false. So $\lVert z\rVert\neq1$ and $z\notin K$.

If $y\cdot u_{i}\neq0$ for some $i\in[k]$, fix such an $i$ and let $\varepsilon=|y\cdot u_{i}|>0$. For $z\in B_{d_{E}}(y,\varepsilon)$, by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §first, The Cauchy-Schwarz Inequality on $\mathbb{R}^n$ §cauchy-schwarz and (F2),

$$|z\cdot u_{i}-y\cdot u_{i}|=|(z-y)\cdot u_{i}|\le\lVert z-y\rVert\,\lVert u_{i}\rVert=\lVert z-y\rVert<\varepsilon .$$

If $z\cdot u_{i}=0$ this would read $|y\cdot u_{i}|<\varepsilon=|y\cdot u_{i}|$, using $|-s|=|s|$ from Rules of Arithmetic and Order in an Ordered Field §absolute-value; this is false. So $z\cdot u_{i}\neq0$ and $z\notin K$.

In both cases $B_{d_{E}}(y,\varepsilon)\subseteq\mathbb{R}^{n}\setminus K$. Hence $\mathbb{R}^{n}\setminus K$ is open in $(\mathbb{R}^{n},d_{E})$ by Open Subset of a Metric Space §open, so it lies in $\mathcal{T}_{d_{E}}$, and $K$ is closed in $(\mathbb{R}^{n},\mathcal{T}_{d_{E}})$ by Closed Subset of a Topological Space §closed.

Step 3: $K$ is compact. Let $\Sigma=\{x\in\mathbb{R}^{n}:\lVert x\rVert=1\}$. It is compact in $(\mathbb{R}^{n},\mathcal{T}_{d_{E}})$ by The Heine-Borel Theorem in $\mathbb{R}^n$, and Compactness of Closed Balls and the Unit Sphere §sphere, and $K\subseteq\Sigma$. By Step 2 and Closed Subsets of Compact Sets Are Compact, and Compact Subsets of a Metric Space Are Closed and Bounded §closed-subset, applied to the topological space $(\mathbb{R}^{n},\mathcal{T}_{d_{E}})$, the compact set $\Sigma$ and its closed subset $K$, the set $K$ is compact in $(\mathbb{R}^{n},\mathcal{T}_{d_{E}})$.

Step 4: a Lipschitz bound for $q$ on $K$. Let $s=\sum_{i=1}^{n}\sum_{j=1}^{n}A_{ij}^{2}$ and $M=1+s$. Each $A_{ij}^{2}$ is $\ge0$ by (F3), so each inner sum is $\ge0$ and $s\ge0$, by Finite Sums in a Commutative Ring and in an Ordered Field: Distributivity, Differences, Telescoping, Constant Terms, Comparison and the Triangle Inequality §nonnegative applied twice. Hence $M=1+s\ge1+0=1>0$ and $M=1+s\ge0+s=s$, by Rules of Arithmetic and Order in an Ordered Field §order-sum (with $0\le1$ and $0<1$ by Rules of Arithmetic and Order in an Ordered Field §squares); and $M^{2}=M\,M\ge M\cdot1=M\ge s$ by (F3) and Rules of Arithmetic and Order in an Ordered Field §order-product. For $x\in\mathbb{R}^{n}$, by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §bound with $m=n$, by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §nonnegative-scaling applied to $s\le M^{2}$ and the factor $\lVert x\rVert^{2}\ge0$ (F3), and by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product for the last equality,

$$\lVert Ax\rVert^{2}\le s\,\lVert x\rVert^{2}\le M^{2}\lVert x\rVert^{2}=(M\lVert x\rVert)^{2},$$

and since $\lVert Ax\rVert\ge0$ and $M\lVert x\rVert\ge0$ (Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §square), (F3) gives

$$\lVert Ax\rVert\le M\lVert x\rVert\qquad(x\in\mathbb{R}^{n}).\tag{1}$$

Let $x,y\in K$. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, $A(x-y)=Ax-Ay$, so by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §first and The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §second,

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

Hence, by Rules of Arithmetic and Order in an Ordered Field §triangle, The Cauchy-Schwarz Inequality on $\mathbb{R}^n$ §cauchy-schwarz, (1) and $\lVert x\rVert=\lVert y\rVert=1$,

$$|q(x)-q(y)|\le|(x-y)\cdot(Ax)|+|y\cdot(A(x-y))|\le\lVert x-y\rVert\,\lVert Ax\rVert+\lVert y\rVert\,\lVert A(x-y)\rVert\le2M\lVert x-y\rVert ,\tag{2}$$

where the last step bounds $\lVert x-y\rVert\,\lVert Ax\rVert\le\lVert x-y\rVert\,(M\lVert x\rVert)=M\lVert x-y\rVert$ by (1) and Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §nonnegative-scaling with the factor $\lVert x-y\rVert\ge0$ (Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §square), bounds $\lVert y\rVert\,\lVert A(x-y)\rVert=\lVert A(x-y)\rVert\le M\lVert x-y\rVert$ by (1), and adds the two bounds by Rules of Arithmetic and Order in an Ordered Field §order-sum, with $M+M=2M$ and $2=1+1$ as in Closure Facts in an Ordered Field: Negatives, Differences, Quotients, Absolute Values, Powers, Natural Numbers, Halves and Minima §two.

Step 5: continuity. Let $f:K\to\mathbb{R}$ be the map $x\mapsto q(x)$, a map into $(\mathbb{R},d_{\mathbb{R}})$ with $d_{\mathbb{R}}(s',t')=|s'-t'|$ as in Metric Spaces: Balls, the Metric Topology, and the Real and Complex Numbers as Metric Spaces §real-line. We show that $f$ is continuous on $K$ as a map from $(\mathbb{R}^{n},d_{E})$ to $(\mathbb{R},d_{\mathbb{R}})$. Let $x'\in K$ and a real $\varepsilon>0$ be given, in this order. Since $M>0$ (so also $0\le M$), $2M=M+M>0+0=0$ by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §strict-sum, so $2M\neq0$ and its reciprocal $(2M)^{-1}$ exists by Negatives, Differences, Reciprocals and Quotients §reciprocal and is $>0$ by Rules of Arithmetic and Order in an Ordered Field §positive-reciprocal. Let $\delta=\varepsilon\,(2M)^{-1}$, which is $>0$ by Rules of Arithmetic and Order in an Ordered Field §order-product, and satisfies $2M\delta=\varepsilon$. If $y\in K$ and $d_{E}(x',y)<\delta$, then by (2) and Step 2's identity $d_{E}(x',y)=\lVert y-x'\rVert$, and by Rules of Arithmetic and Order in an Ordered Field §order-product,

$$d_{\mathbb{R}}(f(y),f(x'))=|q(y)-q(x')|\le2M\lVert y-x'\rVert=2M\,d_{E}(x',y)<2M\delta=\varepsilon .$$

So $f$ is continuous at $x'$ relative to $K$ by Continuous Map Between Metric Spaces §continuous-at, for every $x'\in K$, and hence continuous on $K$ by Continuous Map Between Metric Spaces §continuous.

Step 6: the maximum. By Steps 1, 3 and 5, Extreme Value Theorem on a Compact Subset of a Metric Space §extremes, applied to the metric space $(\mathbb{R}^{n},d_{E})$, the nonempty compact set $K$ and the map $f$, gives $x_{\max}\in K$ with $f(x)\le f(x_{\max})$ for every $x\in K$. With $v=x_{\max}$ this is $x\cdot(Ax)\le v\cdot(Av)$ for every $x\in K$.

Clause eigenvector. Let $v\in K$ with $q(x)\le q(v)$ for every $x\in K$, and let $\lambda=q(v)=v\cdot(Av)$. By (F2), $v\cdot v=1$.

Step (a): if $w\in\mathbb{R}^{n}$, $w\cdot v=0$ and $w\cdot u_{i}=0$ for every $i\in[k]$, then $w\cdot(Av)=0$. Let $a=w\cdot(Av)$ and $b=w\cdot(Aw)-\lambda\,(w\cdot w)$, real numbers; note $v\cdot w=0$ by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §symmetric. Let $t\in\mathbb{R}$ and $z=v+tw\in\mathbb{R}^{n}$. By The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §first, The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §second and The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §symmetric,

$$z\cdot z=v\cdot v+2t\,(v\cdot w)+t^{2}\,(w\cdot w)=1+t^{2}\,(w\cdot w),$$

which is $\ge1+0=1>0$: indeed $t^{2}\ge0$ by (F3) and $w\cdot w\ge0$ by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §nonnegative, so $t^{2}\,(w\cdot w)\ge0$ by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §positive-product, and $1+t^{2}\,(w\cdot w)\ge1+0$ by Rules of Arithmetic and Order in an Ordered Field §order-sum. Let $r=\lVert z\rVert$; then $r\ge0$ and $r^{2}=z\cdot z>0$ by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §square, so $r\neq0$ (as $0^{2}=0$ by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product) and $r>0$. Let $\rho=r^{-1}$, which exists by Negatives, Differences, Reciprocals and Quotients §reciprocal and is $>0$ by Rules of Arithmetic and Order in an Ordered Field §positive-reciprocal, and let $x=\rho z$. Then $|\rho|=\rho$ by Absolute Value in an Ordered Field §absolute-value, so $\lVert x\rVert=\rho\,r=1$ by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §homogeneity; and for $i\in[k]$, as $v\in K$, $x\cdot u_{i}=\rho\,(v\cdot u_{i}+t\,(w\cdot u_{i}))=0$ by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §first. So $x\in K$, and $q(x)\le\lambda$. By Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector and The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §first and The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §second, $q(x)=(\rho z)\cdot(\rho\,(Az))=\rho^{2}q(z)$; and $\rho^{2}r^{2}=(\rho r)^{2}=1$ by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product. So $\rho^{2}q(z)\le\lambda=\rho^{2}(\lambda r^{2})$, and as $\rho^{2}>0$ (by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §sign), Rules of Arithmetic and Order in an Ordered Field §order-product gives $q(z)\le\lambda r^{2}=\lambda+\lambda t^{2}(w\cdot w)$. On the other hand, $A z=Av+t\,(Aw)$ by Algebraic Rules for Matrix Products, Matrix-Vector Products and Transposes §matrix-vector, so by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §first, The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §second and (F1), which gives $v\cdot(Aw)=w\cdot(Av)=a$,

$$q(z)=v\cdot(Av)+t\,(v\cdot(Aw))+t\,(w\cdot(Av))+t^{2}\,(w\cdot(Aw))=\lambda+2ta+t^{2}\,(w\cdot(Aw)).$$

Comparing the two expressions (Rules of Arithmetic and Order in an Ordered Field §order-sum),

$$2ta+t^{2}b\le0\qquad\text{for every }t\in\mathbb{R}.\tag{3}$$

Now let $c=|b|+1$; then $c\ge1>0$ by Rules of Arithmetic and Order in an Ordered Field §absolute-value, so $c^{-1}$ exists by Negatives, Differences, Reciprocals and Quotients §reciprocal. Take $t=a\,c^{-1}$ in (3), so that $tc=a$, and multiply by $c^{2}>0$ (Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §sign, Rules of Arithmetic and Order in an Ordered Field §order-product): $2a\,(tc)\,c+(tc)^{2}b\le0$, that is,

$$a^{2}\,(2c+b)\le0 .$$

Here $2c+b=|b|+(|b|+b)+2\ge2>0$, since $|b|\ge0$ and $-|b|\le b$ by Rules of Arithmetic and Order in an Ordered Field §absolute-value, and $0<2$ by Rules of Arithmetic and Order in an Ordered Field §midpoint. If $a\neq0$, then $a^{2}=a\,a\neq0$ by Rules of Arithmetic and Order in an Ordered Field §zero and $a^{2}\ge0$ by (F3), so $a^{2}>0$ and $a^{2}(2c+b)>0$ by Rules of Arithmetic and Order in an Ordered Field §order-product, a contradiction. Hence $a=w\cdot(Av)=0$.

Step (b): $u_{i}\cdot(Av)=0$ for every $i\in[k]$. Let $i\in[k]$ and let $\mu\in\mathbb{R}$ be such that $u_{i}$ is an eigenvector of $A$ with eigenvalue $\mu$, so $Au_{i}=\mu u_{i}$ by Real Eigenvalues and Eigenvectors of a Real Square Matrix §eigenvector. By Rules for Symmetric and Positive Semidefinite Matrices: Closure, Self-Adjointness, Polarization, Congruence and Cones §self-adjoint, The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §first and The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §symmetric, and as $v\in K$,

$$u_{i}\cdot(Av)=(Au_{i})\cdot v=(\mu u_{i})\cdot v=\mu\,(v\cdot u_{i})=0 .$$

Step (c): conclusion. Let $w=Av-\lambda v\in\mathbb{R}^{n}$. By The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §first, The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §symmetric, $v\cdot v=1$ and Step (b),

$$w\cdot v=(Av)\cdot v-\lambda\,(v\cdot v)=\lambda-\lambda=0,\qquad w\cdot u_{i}=(Av)\cdot u_{i}-\lambda\,(v\cdot u_{i})=u_{i}\cdot(Av)-0=0\quad(i\in[k]).$$

By Step (a), $w\cdot(Av)=0$. Hence, by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §second,

$$w\cdot w=w\cdot(Av)-\lambda\,(w\cdot v)=0,$$

so $w=0$ by The Dot Product on $\mathbb{R}^n$ Is Symmetric, Bilinear and Positive Definite §definite. By Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations §operations and Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations §origin, $(Av)_{l}-\lambda v_{l}=0$, so $(Av)_{l}=(\lambda v)_{l}$ for every $l\in[n]$, and $Av=\lambda v$ by Euclidean Space $\mathbb{R}^n$: n-Tuples of Real Numbers with Their Componentwise Operations §equality. Finally $v\neq0$, since $\lVert v\rVert=1\neq0$ (Fields §field) while the origin has norm $0$ by Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square §vanishing. By Real Eigenvalues and Eigenvectors of a Real Square Matrix §eigenvector, $v$ is an eigenvector of $A$ with eigenvalue $\lambda=v\cdot(Av)$.