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

Step 1: Recognize the structure of the matrix.
The matrix \(A = I_n - \frac{1}{n}\mathbf{1}\mathbf{1}^T\) is the well known centering matrix used in statistics to subtract the mean from a vector.
It is symmetric, since \(A^T = I_n^T - \frac{1}{n}(\mathbf{1}\mathbf{1}^T)^T = I_n - \frac{1}{n}\mathbf{1}\mathbf{1}^T = A\).
It is also idempotent, meaning \(A^2 = A\), which we can check directly.

Step 2: Show A is idempotent.
\[ A^2 = \left(I_n - \frac{1}{n}\mathbf{1}\mathbf{1}^T\right)\left(I_n - \frac{1}{n}\mathbf{1}\mathbf{1}^T\right) = I_n - \frac{2}{n}\mathbf{1}\mathbf{1}^T + \frac{1}{n^2}\mathbf{1}(\mathbf{1}^T\mathbf{1})\mathbf{1}^T \]
Since \(\mathbf{1}^T\mathbf{1} = n\) (the dot product of the all ones vector with itself, summing \(n\) ones), the last term becomes \(\frac{1}{n^2}\mathbf{1}\cdot n \cdot \mathbf{1}^T = \frac{1}{n}\mathbf{1}\mathbf{1}^T\).
\[ A^2 = I_n - \frac{2}{n}\mathbf{1}\mathbf{1}^T + \frac{1}{n}\mathbf{1}\mathbf{1}^T = I_n - \frac{1}{n}\mathbf{1}\mathbf{1}^T = A \]
So \(A\) is idempotent and symmetric, which makes it a projection matrix.

Step 3: Use the property of symmetric idempotent matrices.
A real symmetric matrix is orthogonally diagonalizable, and all its eigenvalues are real.
For an idempotent matrix, if \(\lambda\) is an eigenvalue with eigenvector \(v\), then \(Av = \lambda v\) implies \(A^2v = \lambda^2 v\), but also \(A^2v = Av = \lambda v\).
So \(\lambda^2 v = \lambda v\), which forces \(\lambda^2 = \lambda\), so \(\lambda\) can only be 0 or 1.
For a symmetric matrix, \(x^TAx\) for a unit vector \(x\) is maximized exactly at the largest eigenvalue of \(A\) (the Rayleigh quotient result).
So we only need to check whether \(A\) actually has an eigenvalue equal to 1.

Step 4: Find an eigenvector with eigenvalue 1.
Take any vector \(v\) that is orthogonal to \(\mathbf{1}\), meaning \(\mathbf{1}^Tv = 0\) (its entries sum to zero). Such vectors exist whenever \(n \geq 2\).
\[ Av = \left(I_n - \frac{1}{n}\mathbf{1}\mathbf{1}^T\right)v = v - \frac{1}{n}\mathbf{1}(\mathbf{1}^Tv) = v - \frac{1}{n}\mathbf{1}\cdot 0 = v \]
So every vector orthogonal to \(\mathbf{1}\) is an eigenvector of \(A\) with eigenvalue 1. This subspace has dimension \(n-1\), so 1 is indeed an eigenvalue, with multiplicity \(n-1\).
Picking any unit vector \(x\) from this subspace gives \(x^TAx = x^Tx = 1\).

Step 5: Conclude the maximum.
Since the eigenvalues of \(A\) are only 0 and 1, and 1 is attained, the largest eigenvalue is 1.
So the maximum of \(x^TAx\) over all unit vectors \(x\) is exactly 1.

Final Answer:
The value of \(\max_{S} x^TAx\) is 1. \[ \boxed{1} \]