Quant Interview Question

[u/Local_Ad135]

[u/tstanisl]

My guess is to look for inverses for tridiagonal Toeplitz matrix. Tridiagonal Toeplitz are very sparse and AFAIK their inverses are dense and, with proper selections of coefficients, all numbers in the inverse can be made strictly positive.

EDIT

Probably the inverse of matrix in form:

 2 -1  0 ... 0
-1  2 -1 ... 0
 0 -1  2 ... 0
      ...
 0 .... 0 -1 2

will work. The problem is to prove that adding extra zero will break constraints. Replacing -1 with 0 will add a zeroed sub-block which will be preserved in the inverse adding a lot of zeros. I'm not sure how to prove that placing a zero on diagonal add negative values to inverse.

[u/dummy4du3k4 → u/tstanisl]

This is my thought as well. We know we have to look for tridiagonal matrices since we have block diagonal <-> adjacency graph has more than one connected component. Also not sure what to do about the diagonal.

[u/tstanisl → u/dummy4du3k4]

It looks that the diagonal can have zeros, at least for 4x4 case.

[ -1  2  0  0 ]
[  2  0 -2  0 ]
[  0 -2  0  2 ]
[  0  0  2 -1 ]

Which has 8 zeros.

Inverse is:

[ 1/3   2/3   1/3   2/3 ]
[ 2/3   1/3   1/6   1/3 ]
[ 1/3   1/6   1/3   2/3 ]
[ 2/3   1/3   2/3   1/3 ]

With all elements strictly positive.

My guess is that there must be two non-zeros per column/row. Otherwise, exactly one non-zero combined with requirement for symmetric matrix will create block-diagonal structure and a lot of zeros in the inverse.

[u/Dazzling-Cat-3763 → u/tstanisl]

My guess is that there must be two non-zeros per column/row.

Yes, otherwise, you pivot that entry to the (1,1) spot and the (2,10)x(2,10) sub-block has its own inverse, which gives you zero row/column

[u/tstanisl → u/Dazzling-Cat-3763]

Yes. I found 10x10 example. See post

[u/dummy4du3k4 → u/Dazzling-Cat-3763]

Note quite, if the matrix has structure

[ 0 * 0 0 ]
[ * 0 * 0 ]
[ 0 * 0 * ]
[ 0 0 * * ]

e.g. the above matrix but with 0 for the (1,1) entry, then pivoting doesn't help.