IBM Research

PUZZLE   IBM-301

Computing quadratic forms

IBM Research · Ponder This · 2023-05

IBM Ponder This #301 · May 2023 ​

This problem was suggested by Lorenzo Gianferrari Pini and Radu-Alexandru Todor - thanks!

Let x∈Rn be a length n vector (x0,x1,…,xn−1) and A∈Rn×n be an n×n matrix. We seek to compute the quadratic form xTAx.

Assume x is equally spaced between −1 and 1, e.g., for n=5, we have

x=(−1,−0.5,0,0.5,1)

The matrix A is generated in the following manner:

Let k∈N be a natural number and define a vector a∈R2k that is equally spaced between 0 and 1, i.e., at=t2k−1 for t=0,1,…,2k−1. The values of A will be taken from the vector a in the following manner:

We are given a sequence Q0,Q1,…,Qn−1, with each Qi∈Nk being a vector of k natural numbers. Given two such vectors, define Qi==Qj as the binary vector of length k that has 1s in the entries that are equal in Qi,Qj and 0s in the other entries. Let [Qi==Qj] be the natural number whose binary representation is Qi==Qj, where the least significant bit is on index 0. For example, if

Qi=(1,5,7,8)

Qj=(2,5,6,8)

Then

Qi==Qj=(0,1,0,1)

And

[Qi==Qj] = 10 (since the vector (0,1,0,1) stands for the binary representation 1010).

Now define Aij=a[Qi==Qj].

So one can think of Aij as taking on a value from a fixed list of 2k values based on the "similarity" between Qi and Qj.

The values of the Qi's are chosen pseudo-randomly using the formula

Qi[t]=⌊2k⋅(sin⁡((i+1)⋅(t+1))−⌊sin⁡((i+1)⋅(t+1))⌋)⌋

For example, if k=5, then Q13=(31,8,2,15,24)

Your goal: Find xTAx (rounded to three decimals) for k=5,n=220.

A bonus "*" will be given for finding xTAx (rounded to three decimals) for k=5,n=230.

Solution

Best opened after a real attempt

To be added.