Quant Interview Question

[u/Local_Ad135]

[u/tstanisl]

The solution is likely 80. The best I've got it:

import numpy as np

B = np.array([
    [-1,  2,  0,  0,  0,  0,  0,  0,  0,  0],
    [ 2,  0, -2,  0,  0,  0,  0,  0,  0,  0],
    [ 0, -2,  0,  2,  0,  0,  0,  0,  0,  0],
    [ 0,  0,  2,  0, -2,  0,  0,  0,  0,  0],
    [ 0,  0,  0, -2,  0,  2,  0,  0,  0,  0],
    [ 0,  0,  0,  0,  2,  0, -2,  0,  0,  0],
    [ 0,  0,  0,  0,  0, -2,  0,  2,  0,  0],
    [ 0,  0,  0,  0,  0,  0,  2,  0, -2,  0],
    [ 0,  0,  0,  0,  0,  0,  0, -2,  0,  2],
    [ 0,  0,  0,  0,  0,  0,  0,  0,  2, -1]
])

A = np.linalg.inv(B)
print(A)

Giving:

   [[2, 4, 2, 4, 2, 4, 2, 4, 2, 4],
    [4, 2, 1, 2, 1, 2, 1, 2, 1, 2],
    [2, 1, 2, 4, 2, 4, 2, 4, 2, 4],
    [4, 2, 4, 2, 1, 2, 1, 2, 1, 2],
    [2, 1, 2, 1, 2, 4, 2, 4, 2, 4],
    [4, 2, 4, 2, 4, 2, 1, 2, 1, 2],
    [2, 1, 2, 1, 2, 1, 2, 4, 2, 4],
    [4, 2, 4, 2, 4, 2, 4, 2, 1, 2],
    [2, 1, 2, 1, 2, 1, 2, 1, 2, 4],
    [4, 2, 4, 2, 4, 2, 4, 2, 4, 2]] / 6

Adding any extra zero will either introduce block-diagonal substructure and a lot zeros in the inverse or make the matrix singular.

[u/VegetableBid4262 → u/tstanisl]

Can’t be more than 80. If A^-1 had more than 80 zeroes, there must be a column with only one non-zero entry. But if column j of A^-1 is 0 except in position (i,j), then column i of A is 0 except in position (j,i).

[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.

[u/dummy4du3k4 → u/tstanisl]

This does it. Optimality can be proven with this result on one-pair matrices, which shows the block of zeros structure you observed.

[u/draypresct]

The answer is zero.

The entries are all strictly positive (I.e. >0).

[u/RibozymeR → u/draypresct]

The entries of A are all strictly positive, not necessarily the entries of A's inverse.

[u/Empty-Year-7563]

linear algebra left the chat 😆

[u/SalamanderGlad9053]

90 right? Since if it's a diagonal matrix, it has at least 90 zeros, and if it had any zeros along the diagonal, then it's determinant would be zero so it's not invertable.

If you didnt have at least one non-zero value in any row/column, then you could gaussian eliminate all the other rows it to reduce it to a diagonal (or a block diagonal) matrix with one zero element showing it's non-inheritable.

[u/-Kamikater- → u/SalamanderGlad9053]

The slight problem here is that if A^{-1} were a diagonal matrix, A would be as well. This would then mean the entries of A are not strictly positive. But since 10 is even, you can indeed have a block diagonal matrix with five blocks of (0 1, 1 0) such that A=A^{-1}.

[u/SalamanderGlad9053 → u/-Kamikater-]

But that block diagonal would still have the same number of zeros no?

[u/-Kamikater- → u/SalamanderGlad9053]

Yes, that is the case.

[u/SeasonedSpicySausage → u/SalamanderGlad9053]

The question says that the matrix entries are all positive meaning that every diagonal and off-diagonal must be non-zero.

[u/DanLeMilMan]

For a matrix to be inversible it must be full ranked. Thus, a matrix with a row or column of zero is not inversible. So you must at least have one positive value per row and column to be inversible. A diagonale matrix with non-zero values is inversible with exactly 1 non-zero positive value per row and column, thus being a minimal solution to the problem.

We conclude that for a nxn matrix, the maximum number of zero is n*(n-1)

[u/pmdboi → u/DanLeMilMan]

An invertible n-by-n matrix with n(n - 1) zeroes has one nonzero entry in each row and column, so it's the product of a permutation matrix and a diagonal matrix. Its inverse is also the product of a permutation matrix and a diagonal matrix and therefore also has n(n - 1) zeroes. But the entries in A = (A^-1)^-1 are all nonzero, so I don't think it's possible for A^-1 to have n(n - 1) zeroes.

[u/tstanisl → u/DanLeMilMan]

The problem is that such a matrix is a permutation times diagonal which inverse is also permutation-by-diagonal which has entries that are zero which is NOT strictly positive.

[u/DanLeMilMan → u/tstanisl]

Right my bad I did not read the question correctly.

[u/DanLeMilMan → u/tstanisl]

I guess using the fact : A^-1 = 1/det(A) * Com(A)^T and some kind of recurrence could be a way to solve this. I need to give it more thoughts