2026 USAAIO Round 1 Sample problems, Problem 2

AI Olympiads
1

Problem 2

Consider matrix A\in\mathbb{R}^{4\times4}. For any vector

x=\begin{bmatrix}x_{0}\\ x_{1}\\ x_{2}\\ x_{3}\end{bmatrix}

we have

Ax=\begin{bmatrix}x_{2}\\ x_{3}\\ x_{1}\\ x_{0}\end{bmatrix}.

Part 2.1

What operation A does on x?

  • A. Rotation.
  • B. Reflection.
  • C. Permutation.
  • D. Dilation.
  • E. Translation.

Part 2.2

Write A in the matrix form. Reasoning is not required.

Part 2.3

We can write A in the following decomposition form:

A=\sum_{i=0}^{3}\hat{e}^{(f(i))}\hat{e}^{(i),\top},

where \hat{e}^{(i)}\in\mathbb{R}^{4} is a column unit vector whose $i$th component is equal to 1 and all other components are equal to 0, and f(i)\in\{0,1,2,3\} for i\in\{0,1,2,3\}.

Compute f(0), f(1), f(2) and f(3). Reasoning is not required.

2 Likes
2

Part 2.1

C. Permutation

Part 2.2

\begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}

Part 2.3

𝑓⁑(0)=3, 𝑓⁑(1)=2, 𝑓⁑(2)=0, 𝑓⁑(3)=1

2 Likes
3

Simple explanation:

Part 2.1

It is a (C.) Permuation because it is a rearrangement of the rows of x .

Part 2.2

\mathbf{A} \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix} x_2 \\ x_3 \\ x_1 \\ x_0\end{bmatrix}

\mathbf{A} must be made of 1’s and 0’s because the values of \mathbf{A}x are all the same.

Say \mathbf{A} = \begin{bmatrix} a_{00} & a_{01} & a_{02} & a_{03} \\ a_{10} & a_{11} & a_{12} & a_{13} \\ a_{20} & a_{21} & a_{22} & a_{23}\\ a_{30} & a_{31} & a_{32} & a_{33}\end{bmatrix},

Most people with a good understanding of matrix mutiplication would skip this next step.

then we can write \mathbf{A}x as \begin{bmatrix} a_{00}x_0 + a_{01}x_1 + a_{02}x_2 + a_{03}x_3\\ a_{10}x_0 + a_{11}x_1 + a_{12}x_2 + a_{13}x_3\\ a_{20}x_0 + a_{21}x_1 + a_{22}x_2 + a_{23}x_3\\ a_{30}x_0 + a_{31}x_1 + a_{32}x_2 + a_{33}x_3\end{bmatrix}

which is quite the mouthful! But now, because the top value of \mathbf{A}x is x_2, we know that a_{02} is 1, and all the other 1\text{st} row coefficients are 0’s.

So now, our matrix looks like this: \mathbf{A} = \begin{bmatrix} 0 & 0 & 1 & 0 \\ a_{10} & a_{11} & a_{12} & a_{13} \\ a_{20} & a_{21} & a_{22} & a_{23}\\ a_{30} & a_{31} & a_{32} & a_{33}\end{bmatrix},

Following the same steps for the next few rows, we get

\boxed{\mathbf{A} = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 &1 & 0 & 0\\ 1 & 0 & 0 & 0\end{bmatrix} }

(You could also trace each element directly to \mathbf{A} without needing to write it out, saving much time.)

Part 2.3

Let’s break down the problem: We want to multiply a column vector of length 4 by a row vector of length 4

This is (4,1) \times (1,4), so we will get a full (4,4) matrix out each time.

Because i ranges from 0 to 3, we have 4 matrices that we add together to get \mathbf{A}. Taking a closer look, the product of a 4 by 4 column times unit matrix looks like this:

\begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ c_3 \end{bmatrix} \begin{bmatrix} r_0 & r_1 & r_2 & r_3 \end{bmatrix} = \begin{bmatrix} c_0 r_0 & c_0 r_1 & c_0 r_2 & c_0 r_3 \\ c_1 r_0 & c_1 r_1 & c_1 r_2 & c_1 r_3\\ c_2 r_0& c_2 r_1 & c_2 r_2 & c_2 r_3\\ c_3 r_0& c_3 r_1 & c_3 r_2 & c_3 r_3\end{bmatrix}

(Again, an experienced LA user would skip this part)

Now, \hat{e}^{(i)\top} dictates which column the 1 goes in. Because of the summation, when i=0, we must find f(0) such that the 1 goes where it would in the first column of \mathbf{A}.

Because the first column has it’s 1 at the very last index (0,3) this means f(0) = 3.

Repeating this process for increasing values of i (expanding the summation), the answer is \boxed{f(0) = 3, f(1) = 2, f(2) = 0, f(3) = 1}
:grin:

3 Likes