Question

Let \( M = \left(I_n - \frac{1}{n} 11^T \right) \) be a matrix where \( 1 = (1,1,\dots,1)^T \in \mathbb{R}^n \) and \( I_n \) is the identity matrix of order \( n \). The value of \[ \max_{x \in S} x^T M x \] where \[ S = \{ x \in \mathbb{R}^n \mid x^T x = 1 \} \] is ________. 

Hint:

Recognizing special matrices can save a lot of time. The matrix $M = I - \frac{1}{n}J$ is the centering matrix used in statistics (e.g., in PCA). Knowing it's a projection matrix immediately tells you its eigenvalues are 0 and 1, making problems like this trivial.

Answer 1

Correct Answer: 1

Step 1: Understanding the Question:
The problem asks for the maximum value of the quadratic form $x^T M x$ for a unit vector $x$ (since $x^T x = ||x||^2 = 1$). This is a standard result from linear algebra.
Step 2: Key Formula or Approach:
For any symmetric matrix M, the maximum value of the Rayleigh quotient $\frac{x^T M x}{x^T x}$ is equal to the largest eigenvalue of M. Since the constraint is $x^T x = 1$, we just need to find the maximum value of $x^T M x$, which is simply the largest eigenvalue of M.
The matrix $M = I - \frac{1}{n}11^T$ is known as the centering matrix. It is a projection matrix. The eigenvalues of a projection matrix can only be 0 or 1.
Step 3: Detailed Explanation:
Let's prove that M is a projection matrix. A matrix P is a projection matrix if it is idempotent ($P^2 = P$) and symmetric ($P^T = P$).
- Symmetry: Let $J = 11^T$ (a matrix of all ones). $J$ is symmetric. \[ M^T = (I - \frac{1}{n}J)^T = I^T - \frac{1}{n}J^T = I - \frac{1}{n}J = M \] So, M is symmetric.
- Idempotence: We need to compute $M^2$. \[ M^2 = (I - \frac{1}{n}J)(I - \frac{1}{n}J) = I^2 - \frac{1}{n}J - \frac{1}{n}J + \frac{1}{n^2}J^2 = I - \frac{2}{n}J + \frac{1}{n^2}J^2 \] We need to find $J^2 = (11^T)(11^T) = 1(1^T1)1^T$. The inner product $1^T1 = \sum_{i=1}^n 1^2 = n$. So, $J^2 = 1(n)1^T = n(11^T) = nJ$. Substitute this back into the expression for $M^2$: \[ M^2 = I - \frac{2}{n}J + \frac{1}{n^2}(nJ) = I - \frac{2}{n}J + \frac{1}{n}J = I - \frac{1}{n}J = M \] Since $M^2 = M$, the matrix is idempotent.
Since M is a projection matrix, its eigenvalues can only be 0 or 1. The matrix is not the zero matrix, so it must have at least one eigenvalue equal to 1. The largest possible eigenvalue is 1.
Therefore, the maximum value of $x^T M x$ for a unit vector x is the largest eigenvalue of M, which is 1.
Step 4: Final Answer:
The maximum value is 1.