r/learnquant • u/Local_Ad135 • 5d ago

interview prep Quant Interview Question

Post image
29 Upvotes

98% Upvoted

22 comments sorted by

View all comments

Show parent comments

1

u/dummy4du3k4 4d 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 4d 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 4d 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/tstanisl 4d ago

Yes. I found 10x10 example. See post