← Hudson River Trading Interview Insights

Hudson River Trading·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Apr 2026

Summary

HRT quant engineer interview, one question that spiraled into a pretty intense linear algebra rabbit hole. The follow-ups were where things got interesting.

Questions Asked (1)

Q1

Given an m by n matrix where every row sums to 1 and every column sums to 1, does the matrix have to be square? And if so, is it invertible? What if the matrix raised to the 7th power equals zero?

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

The square part clicked fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Break the problem into three parts: first, prove that the matrix must be square by summing all entries in two ways; second, determine invertibility by analyzing the eigenvalue 1 and the all-ones vector; third, address the nilpotent case by showing it contradicts the row/column sum property unless the matrix is zero, which is impossible. Use clear, logical steps and state assumptions explicitly.

Pro tip: Don't just answer yes/no—explain the reasoning behind each conclusion, as interviewers at Hudson River Trading value rigorous thinking and the ability to handle edge cases. If you're unsure, walk through a small example (e.g., 2x2) to build intuition before generalizing.

1. Prove the matrix must be square

Sum all entries row-wise: since each of the m rows sums to 1, total sum = m. Sum column-wise: since each of the n columns sums to 1, total sum = n. Therefore m = n, so the matrix is square.

2. Analyze invertibility via eigenvalues

The all-ones vector is a right eigenvector with eigenvalue 1 (since each row sums to 1). Similarly, the all-ones vector is a left eigenvector with eigenvalue 1 (since each column sums to 1). Thus 1 is an eigenvalue, but this alone does not guarantee invertibility. However, for a doubly stochastic matrix, the eigenvalue 1 is simple (Perron-Frobenius), and all other eigenvalues have magnitude ≤ 1. Invertibility requires that 0 is not an eigenvalue. Since the matrix is doubly stochastic, it is invertible if and only if no eigenvalue is 0. But the question asks 'is it invertible?'—the answer is not necessarily; e.g., the matrix [[0.5,0.5],[0.5,0.5]] has eigenvalue 0 and is not invertible. So the answer is: not necessarily invertible.

3. Address the nilpotent case (A^7 = 0)

If A^7 = 0, then A is nilpotent, so all eigenvalues are 0. But we already know 1 is an eigenvalue (from row sums). Contradiction. Therefore no such matrix exists (unless the matrix is 0, but then row sums would be 0, not 1). So the condition A^7 = 0 cannot hold for a non-zero doubly stochastic matrix.

4. Summarize conclusions

State clearly: (1) The matrix must be square. (2) It is not necessarily invertible; it is invertible iff 0 is not an eigenvalue. (3) If A^7 = 0, then A must be the zero matrix, which contradicts the row/column sum condition, so no such matrix exists.

Key Points to Mention

  • Summing rows and columns to prove m = n.
  • The all-ones vector as an eigenvector with eigenvalue 1 for both left and right.
  • Perron-Frobenius theorem for nonnegative matrices: eigenvalue 1 is simple and dominant.
  • Invertibility condition: determinant ≠ 0, equivalently 0 is not an eigenvalue.
  • Nilpotent matrix has all eigenvalues 0, contradicting the existence of eigenvalue 1.
  • Example of a non-invertible doubly stochastic matrix (e.g., all entries 1/n).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.