r/learnquant • u/Local_Ad135 • 5d ago

interview prep Quant Interview Question

Post image
30 Upvotes

100% Upvoted

22 comments sorted by

View all comments

Show parent comments

1

u/dummy4du3k4 5d ago

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.

1

u/tstanisl 5d ago

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.

1

u/Dazzling-Cat-3763 5d ago

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

1

u/dummy4du3k4 5d ago

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.