2025 USA-NA-AIO Round 1, Problem 1, Part 4

AI Olympiads 2025 USA-NA-AIO Round 1
1

Part 4 (10 points, non-coding task)

In this part, you are asked to prove a general result that holds for any real-valued symmetric matrix.

Let \mathbf{U} \in \Bbb R^{N \times N} be a real-valued symmetric matrix.

Consider the following eigenvalue equation

\mathbf{U} \mathbf{v} = \lambda \mathbf{v} ,

where \lambda \in \Bbb R and \mathbf{v} \in \Bbb R^{N \times 1}.

Let \lambda_i and \lambda_j be two distinct real eigenvalues and \mathbf{v}_i, \mathbf{v}_j \in \Bbb R^{N \times 1} be two eigenvectors associated with them, respectively.

Prove that

\mathbf{v}_i^\top \mathbf{v}_j = 0 .

That is, vectors \mathbf{v}_i and \mathbf{v}_j are orthogonal.

2

\color{green}{\text{WRITE YOUR SOLUTION IN THIS TEXT CELL.}}

We use two approaches to compute

\mathbf{v}_i^\top \mathbf{U} \mathbf{v}_j .

Approach 1

We have

\begin{align*} \mathbf{v}_i^\top \mathbf{U} \mathbf{v}_j & = \mathbf{v}_i^\top \left( \mathbf{U} \mathbf{v}_j \right) \\ & = \mathbf{v}_i^\top \left( \lambda_j \mathbf{v}_j \right) \\ & = \lambda_j \mathbf{v}_i^\top \mathbf{v}_j . \hspace{1cm} (1) \end{align*}

Approach 1

We have

\begin{align*} \mathbf{v}_i^\top \mathbf{U} \mathbf{v}_j & = \left( \mathbf{v}_i^\top \mathbf{U} \right) \mathbf{v}_j \\ & = \left( \mathbf{v}_i^\top \mathbf{U}^\top \right) \mathbf{v}_j \\ & = \left( \mathbf{U} \mathbf{v}_i \right)^\top \mathbf{v}_j \\ & = \left( \lambda_i \mathbf{v}_i \right)^\top \mathbf{v}_j \\ & = \lambda_i \mathbf{v}_i^\top \mathbf{v}_j , \hspace{1cm} (2) \end{align*}

where the second equality follows from the property that \mathbf{U} is a symmetric matrix.

Two approaches should yield the same result. Equating (1) and (2), we have

\lambda_j \mathbf{v}_i^\top \mathbf{v}_j = \lambda_i \mathbf{v}_i^\top \mathbf{v}_j .

Because \lambda_i \neq \lambda_j, we must have

\mathbf{v}_i^\top \mathbf{v}_j = 0 .

This completes the proof.

\color{red}{\text{""" END OF THIS PART """}}