Question

Let \(A = \left(I_n - \frac{1}{n}\mathbf{1}\mathbf{1}^T\right)\) be a matrix, where \(\mathbf{1} = (1,1,1,\ldots,1)^T \in \mathbb{R}^n\) and \(I_n\) is the identity matrix of order \(n\).

The value of \(\max_{S} x^TAx\), where \(S = \{x \in \mathbb{R}^n \mid x^Tx = 1\}\), is __________. (Answer in integer)

Hint:

Check that \(A\) is symmetric and idempotent (\(A^2=A\)), so its eigenvalues can only be 0 or 1. The maximum of \(x^TAx\) on the unit sphere equals the largest eigenvalue.

Answer 1

Correct Answer: 1

This question asks for the maximum of the quadratic form $x^TAx$ over all unit vectors, a classic constrained optimization problem. Instead of jumping straight to eigenvalue facts, let's set it up with Lagrange multipliers first and then work out the actual numbers for this specific matrix $A$.

Setting up the optimization: We want to maximize $f(x) = x^TAx$ subject to $g(x) = x^Tx - 1 = 0$. At the maximum, the gradients must be parallel: $\nabla f = \lambda \nabla g$ for some scalar $\lambda$. Since $A$ is symmetric, $\nabla f = 2Ax$ and $\nabla g = 2x$, so this condition reduces to $Ax = \lambda x$. In other words, the maximizer $x$ must be a unit eigenvector of $A$, and the maximum value of $x^TAx$ equals the corresponding eigenvalue $\lambda$, since at an eigenvector $x^TAx = x^T(\lambda x) = \lambda(x^Tx) = \lambda$.

Finding the eigenvalues by testing vectors directly: Rather than proving the general idempotent-matrix fact first, plug in two natural test vectors.

1. Test $x = \frac{1}{\sqrt{n}}\mathbf{1}$ (unit vector along the all-ones direction): $\mathbf{1}^Tx = \frac{1}{\sqrt{n}}(\mathbf{1}^T\mathbf{1}) = \frac{n}{\sqrt{n}} = \sqrt{n}$. So $Ax = x - \frac{1}{n}\mathbf{1}(\mathbf{1}^Tx) = x - \frac{1}{n}\mathbf{1}\sqrt{n} = x - \frac{1}{\sqrt{n}}\mathbf{1} = x - x = 0$. This direction gives eigenvalue 0, so $x^TAx = 0$ here, not the maximum.
2. Test any unit $x$ with $\mathbf{1}^Tx = 0$ (entries summing to zero, for example $x = \frac{1}{\sqrt{2}}(1,-1,0,\ldots,0)^T$): $Ax = x - \frac{1}{n}\mathbf{1}(\mathbf{1}^Tx) = x - \frac{1}{n}\mathbf{1}\cdot 0 = x$. So $x^TAx = x^Tx = 1$. This direction gives eigenvalue 1.

Squaring $A$ shows $A^2=A$, so for any eigenvalue $\lambda$ we get $\lambda^2=\lambda$, forcing $\lambda \in \{0,1\}$ only. We already found a direction giving 0 and a direction giving 1, so no other value is possible, and the largest achievable value of $x^TAx$ on the unit sphere is 1.

Let's summarize:

• The maximizer of $x^TAx$ on the unit sphere is always a top eigenvector of $A$, by Lagrange multipliers.
• Testing the all-ones direction gives eigenvalue 0, and any zero-sum direction gives eigenvalue 1.
• Squaring $A$ confirms these are the only two possible eigenvalues.

So $\max_{S} x^TAx = 1$.

\[ \boxed{1} \]