2026 USAAIO Round 1 Sample problems, Problem 5

AI Olympiads
1

Problem 5.

Consider a dataset with N samples \{ x^{(n)} \in \mathbb{R} \}_{n=0}^{N-1} with N \ge 1000. Let \phi\!\left(x^{(n)}\right) \in \mathbb{R}^d be a feature function of x^{(n)}.

Define the kernel function

\kappa_{ij}= \phi\!\left(x^{(i)}\right)^{\top} \phi\!\left(x^{(j)}\right).

Define the kernel matrix

K = \begin{bmatrix} \kappa_{00} & \kappa_{01} & \cdots & \kappa_{0(N-1)} \\ \kappa_{10} & \kappa_{11} & \cdots & \kappa_{1(N-1)} \\ \vdots & \vdots & \ddots & \vdots \\ \kappa_{(N-1)0} & \kappa_{(N-1)1} & \cdots & \kappa_{(N-1)(N-1)} \end{bmatrix}.

Part 5.1

Suppose

\kappa_{ij}=1 + x^{(i)}x^{(j)} + \left(x^{(i)}x^{(j)}\right)^2.

Compute \phi(x).

(Reasoning is not required.)

Part 5.2

Suppose \kappa_{ij}=\left(1 + x^{(i)}x^{(j)} + 2\left(x^{(i)}x^{(j)}\right)^2\right)^2.

Compute \phi(x).

(Reasoning is not required.)

Part 5.3

Suppose
\kappa_{ij}=\left(1 + x^{(i)}x^{(j)} + 2\left(x^{(i)}x^{(j)}\right)^2\right)^2.
Compute the rank of K.
(Reasoning is required.)

Part 5.4

Let
\Phi =\begin{bmatrix}\phi\!\left(x^{(0)}\right)^{\top} \\ \phi\!\left(x^{(1)}\right)^{\top} \\ \vdots \\ \phi\!\left(x^{(N-1)}\right)^{\top}\end{bmatrix}\in \mathbb{R}^{N \times d}.

Suppose \Phi has the singular value decomposition (SVD)

\Phi = U \Sigma V^{\top}.

Write the trace and the determinant of K in terms of the SVD of \Phi.

(Reasoning is required.)

Part 5.5

This is a coding task.
Copy the following code:

import numpy as np

Write a function in the following way.
The input is \{ x^{(n)} \in \mathbb{R} \}_{n=0}^{N-1} (a one-dimensional NumPy array with shape (N,)).
The return is the kernel matrix K with \kappa_{ij}=\left(1 + x^{(i)}x^{(j)} + 2\left(x^{(i)}x^{(j)}\right)^2\right)^2.

In your code, do NOT use any loop. Do NOT use np.linalg.

1 Like
2

Part 5.1

\phi(x) = \begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix}

Part 5.2

\phi(x) = \begin{bmatrix} 1 \\ \sqrt{2}x \\ \sqrt{5}x^2 \\ 2x^3 \\ 2x^4 \end{bmatrix}

Part 5.3

From Part 5.2, we established that the feature map \phi(x) maps input data to a 5-dimensional space (\mathbb{R}^5).The kernel matrix K can be written as K = \Phi \Phi^{\top}, where \Phi is the matrix containing the feature vectors \phi(x^{(n)}) as rows (or columns). The rank of the kernel matrix K is equal to the rank of the set of feature vectors \{\phi(x^{(0)}), \dots, \phi(x^{(N-1)})\}. Given that N \ge 1000 and assuming the dataset contains at least 5 distinct values (which is statistically certain for a sample of this size from \mathbb{R}), the vectors [1, x, x^2, x^3, x^4]^{\top} will span the entire 5-dimensional space (due to the properties of Vandermonde matrices). Therefore, the rank is limited by the dimension of the feature space d=5.

Part 5.4

Let the Singular Value Decomposition (SVD) of \Phi be \Phi = U \Sigma V^{\top}.The kernel matrix is K = \Phi \Phi^{\top}.Substituting the SVD:

K = (U \Sigma V^{\top}) (U \Sigma V^{\top})^{\top} = U \Sigma V^{\top} V \Sigma^{\top} U^{\top}

Since V is orthogonal (V^{\top}V = I):

K = U (\Sigma \Sigma^{\top}) U^{\top}

The non-zero eigenvalues of K are the diagonal elements of \Sigma \Sigma^{\top}, which are the squared singular values of \Phi. Let these singular values be \sigma_i.

The trace of a matrix is the sum of its eigenvalues.

\text{Trace}(K) = \sum_{i} \sigma_i^2

The determinant is the product of the eigenvalues. The matrix K has shape N \times N with N \ge 1000. However, the rank of K is d=5 (from Part 5.2/5.3). Because N > 5, the matrix K is rank-deficient (singular). Therefore, at least one (and actually N-5) eigenvalue is 0.

\text{Determinant}(K) = 0

Part 5.5

import numpy as np

def compute_kernel_matrix(x):
    x_col = x[:, np.newaxis]
    x_row = x[np.newaxis, :]
    P = x_col * x_row
    inner_term = 1 + P + 2 * (P ** 2)
    K = inner_term ** 2
    return K
1 Like