Quant puzzles, solved step by step

Puzzles
100
Traced to a firm
71
Topics
12
Hard
30
Topic
All topicsLogic and algorithmic reasoning10Conditional probability and Bayes7Counting and combinatorics8Continuous and geometric probability9Correlation, regression and linear algebra9Market making, betting and sizing9Expected value and optimal stopping9Statistics and estimation9Pricing, options and index maths7Games and strategic reasoning8Markov chains and random walks7Mental maths and number sense8
Level
AnyWarm upCoreHard
Source
AnyReported at a firmStandard
Showing 1–1 of 1 · filtered from 100Clear filters
  1. 078Let A be the 2 by 2 matrix with 2 on the diagonal and 1 off the diagonal. Compute A to the power 10 without multiplying it out ten times.Correlation, regression and linear algebraCoreQuant researchQuant trading

    Try it first

    What is the top-left entry of A^10?

    Show the worked solution

    A^10 has 29,525 on the diagonal and 29,524 off it. A has eigenvalue 3 along (1, 1) and eigenvalue 1 along (1, -1). Writing A = Q D Q^T with D = diag(3, 1), the tenth power is Q D^10 Q^T, and only the numbers 3 and 1 get raised to the tenth. The entries are (3^10 + 1)/2 and (3^10 - 1)/2.

    Why look for eigenvectors at all?

    Think of a photocopier set to 300% on one axis and 100% on the other. Copy a copy ten times and you do not need to simulate every pass: that axis is 3 to the tenth times longer and the other is unchanged. An eigenvector is a direction the matrix only stretches, so applying the matrix ten times along it is just multiplying by the eigenvalue ten times. Symmetric matrices always have a full set of such directions at right angles, which is what makes this matrix easy.

    Find them by inspection. Adding the two rows of A gives 3 in each, so A(1, 1) = (3, 3): eigenvalue 3. Subtracting gives 1, so A(1, -1) = (1, -1): eigenvalue 1. The trace is 4 and the determinant is 3, and 3 + 1 = 4 and 3 x 1 = 3, which confirms both in one line.

    Two directions the matrix only stretches: powers become powers of numbersxy(1, 1)A(1, 1) = (3, 3)(1, -1) = A(1, -1)eigenvalue 3 along (1, 1); eigenvalue 1 along (1, -1)A = Q D Q^TQ holds the unit eigenvectors, D = diag(3, 1)A^10 = Q D^10 Q^Tthe Q^T Q pairs in the middle cancelD^10 = diag(59,049, 1)only two numbers get raised to the 10thA^10: diagonal (3^10 + 1)/2, off it (3^10 - 1)/229,52529,52429,52429,525
    The matrix stretches the direction (1, 1) by a factor of 3 and leaves (1, -1) unchanged, so A to the tenth stretches them by 59,049 and 1, and converting back to ordinary coordinates gives 29,525 on the diagonal and 29,524 off it.
    The relationship
    A=Q(3001)QT,  Q=12(111−1)⇒A10=12(310+1310−1310−1310+1)A = Q\begin{pmatrix}3&0\\0&1\end{pmatrix}Q^{T},\; Q=\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix} \Rightarrow A^{10} = \tfrac12\begin{pmatrix}3^{10}+1 & 3^{10}-1\\ 3^{10}-1 & 3^{10}+1\end{pmatrix}
    Qthe matrix whose columns are the unit eigenvectors
    Dthe diagonal matrix of eigenvalues, 3 and 1
    Q^Tthe transpose of Q, which is also its inverse
    What it says in wordsRotate into the eigenvector directions, raise each eigenvalue to the tenth, and rotate back.

    Is there an even faster route for this particular matrix?

    Yes. Write A = I + J, where J is the all-ones matrix. J squared is 2J, so every power of J is a multiple of J, and (I + J)^n collapses to I + ((3^n - 1)/2) J. For n = 10 that is I + 29,524 J, which gives 29,525 on the diagonal and 29,524 off it: the same answer, and a good cross-check to say aloud. A brute-force multiplication in code agrees exactly.

    Say why this matters on a desk. A covariance matrix with equal variances and one common correlation has exactly this shape, and its eigenvectors are the market direction and the spread directions. Powers of transition matrices in Markov chains are computed the same way, and the eigenvalue closest to 1 tells you how fast the chain forgets where it started.

    Where candidates lose it

    The fast wrong answer raises each entry to the tenth, giving 1,024 on the diagonal and 1 off it. Matrix multiplication mixes rows and columns, so entries do not power separately; A squared already has 5 on the diagonal, not 4.

    The second loss is diagonalising correctly and then fumbling the conversion back. The Q matrix carries a 1/sqrt(2) on each side, which becomes the factor of one half in the final answer. Check with the trace: the diagonal entries of A^10 must sum to 3^10 + 1.

    What the interviewer asks next

    • What is A^n as n grows large, after dividing by 3^n?
    • Compute the square root of A, a symmetric matrix B with B squared equal to A.
    • Generalise: an n by n matrix with a on the diagonal and b everywhere else. What are its eigenvalues?