Find the minimum value of the quadratic form $x^TMx$ and the corresponding $x$, where $M$ is a symmetric matrix

Question

How do you find the minimum value of the quadratic form $x^TMx$ and the corresponding $x$, where $M$ is a symmetric matrix? I have $x^TMx = x^T(I − 2(vv^T)/\|v\|^2)x$, and I don't know how to continue.

Let $v\in R^{n}$ be a nonzero vector, and $I\in R^{n\times n}$ be an identity matrix. $M = I - 2\frac{vv^{T}}{\lVert v\rVert^{2}}$ is symmetric and satisfies $M^{-1} = M$.

Given $x\in R^{n}$ and $\lVert x\rVert =1$ and the M in the above question, find the minimum value of the quadratic form $x^{T}Mx$ and the corresponding $x$.

Answer 1

$M$ is symmetric. Therefore the minimum of $x^TMx$ with $\|x\|=1$ is the minimum eigenvalue of $M$, which is equal to $-1$ because $M$ is a reflection.

Alternatively, let $u=v/\|v\|$. Then $x^TMx=1-2(x^Tu)^2$. You may use Cauchy-Schwarz inequality to prove that $x^TMx\ge-1$. Now if you can find a unit vector $x$ such that $x^TMx=-1$, you may conclude that the minimum possible value of $x^TMx$ is $-1$.

Answer 2

Part I: Minimum value of $x^TAx$

Your notes must have that the minimum value of $x^TAx$ is the minimum eigenvalue of $A$ if

1. $A$ is symmetric, i.e. $A=A^T$

2. $A$ is involutory i.e. $A=A^{-1}$

3. $x$ is a unit vector i.e. $x^Tx = |x|^2 = 1$, i.e. $|x|=1$.

See here for a proof.

Note: A symmetric involutory matrix $A$ is orthogonal, i.e. $A^T=A^{-1}$.

---

Part II: Minimum eigenvalue of $A$

Next, we compute the eigenvalues of $A$ by evaluating this strange expression in 2 ways: $$x^T A^T Ax$$

First evaluation: $$x^T A^T Ax = (Ax)^T(Ax) = |Ax|^2 = |\lambda x|^2 \stackrel{(*)}{=} \lambda^2 |x|^2 = \lambda^2 (1) = \lambda ^2$$

Second evaluation: $$x^T A^T Ax = x^T (A^T) Ax = x^T (A) Ax = x^T (A^{-1}) Ax = x^Tx = |x|^2 = 1$$

Therefore, $\lambda^2 = 1$, i.e. $\lambda = \pm 1$.

The smaller of these two is -1.

Note: The eigenvalues are $\pm 1$ alternatively because $A$ is orthogonal, i.e. $A^T=A^{-1}$. Here, $A$ is orthogonal because $A^T=A=A^{-1}$, i.e. $A$ is orthogonal because $A$ is symmetric and involutory.

---

Part III: The/An $x$ that corresponds to $-1$:

Based on user1551's comment, let's try:

$$x=\frac{v}{|v|}$$

$$x^TAx = \frac{v^T}{|v|}(I - 2 \frac{vv^T}{|v|^2})(\frac{v}{|v|})$$

$$ = \frac{v^T}{|v|}\frac{v}{|v|} - 2 \frac{v^T}{|v|}\frac{vv^T}{|v|^2}\frac{v}{|v|}$$

$$ = \frac{|v|^2}{|v|^2} - 2 \frac{v^T(vv^T)v}{|v|^4}$$

$$ = \frac{|v|^2}{|v|^2} - 2 \frac{(v^Tv)(v^Tv)}{|v|^4}$$

$$ = \frac{|v|^2}{|v|^2} - 2 \frac{|v|^2|v|^2}{|v|^4}$$

$$ = 1 - 2 = -1$$

-

I thought $x$ is the vector with $0$ in every position except the $i$th position with would have value $1$ where $i$ refers to the the $i$th eigenvalue that corresponds to the minimum eigenvalue $\lambda_i$ because of my answer here: Minimum of a quadratic form but then I realised that I'm referring not to $x$ itself but to $y=U^Tx$, where $U$ is the orthogonal matrix whose columns are the eigenvectors of $A$ and is in the eigendecomposition of $A$: $A=UDU^T$, where $D$ is the corresponding diagonal matrix whose entries are the eigenvalues of A. Therefore, I guess we have

$$x=(U^T)^{-1}y=Uy$$

Because $y$ is 0 everywhere but $i$th entry which is $1$, multiplying $y$ on the right hand side of $U$ will extract the $i$th column of $U$, i.e. the $i$th eigenvector of $A$.

Therefore $x$ is the $i$th eigenvector of $A$.

Now why does $x$, the $i$th eigenvector, i.e.e the eigenvector that corresponds to the $i$th eigenvalue $\lambda_i$ where $\lambda_i = \lambda_{\min}$ turn out to be $\frac{v}{|v|}$? It does simply because $\frac{v}{|v|}$ is the eigenvector that corresponds to the $\lambda_{\min}$! Let's prove it.

Pf: $$(I-2\frac{vv^T}{|v|^2})(x)$$

$$ = (I-2\frac{vv^T}{|v|^2})(\frac{v}{|v|}) = \frac{v}{|v|}-2\frac{(vv^T)(v)}{|v|^3}$$

$$ = \frac{v}{|v|}-2\frac{v(v^Tv)}{|v|^3} = \frac{v}{|v|}-2\frac{v|v|^2}{|v|^3}$$

$$ = \frac{v}{|v|}-2\frac{v}{|v|} = -\frac{v}{|v|} = -1\frac{v}{|v|}$$

$$ = \lambda_{\min}\frac{v}{|v|}$$

Therefore,

$$(I-2\frac{vv^T}{|v|^2})(\frac{v}{|v|}) = \lambda_{\min}\frac{v}{|v|}$$

QED

---

$(*)$

$$|\lambda x|^2 = (\lambda x)^T(\lambda x) = \lambda (x)^T(\lambda x) = \lambda (x)^T(\lambda) (x) = \lambda^2 (x)^T(x) = \lambda^2 |x|^2 \ \text{not sure}$$