# How do I prove that the inverse of the matrix, M, below has all elements greater than or equal to 0?

$M= \begin{bmatrix} 1 & \nu & 0 & ... & 0 & -\nu \\ -\nu & 1 & \nu & 0 & ... & 0 \\ 0 & -\nu & 1 & \nu & ... & 0 \\ 0 & 0 & -\nu & 1 & \nu.. & 0 \\ .& & .& .& .& \\ \nu & 0 & ... & 0 & -\nu & 1 \\ \end{bmatrix}$

It is basically a Circulant matrix.

How do I prove that the inverse of this matrix will have all positive entries. For what conditions of $\nu$ will it be a non-negative matrix ?

(Needs too much space to be a comment, so an answer it is)

As in the case of all circulant matrices you can find the inverse by using the discrete Fourier transform. The eigenvectors of the $N\times N$ version $M(N,\nu)$ of your matrix are $(1,\zeta^j,\zeta^{2j},\ldots,\zeta^{(N_1)j})^T$, where $j=0,1,\ldots,N-1,$ $\zeta=e^{2\pi i/N}$ and $$M(N,\nu)x_j=\lambda_jx_j,\qquad \lambda_j=(1-2i\nu\sin\frac{2\pi j}N).$$ The inverse $M(n,\nu)^{-1}$ is then the circulant matrix with coefficients gotten from the IDFT of $(1/\lambda_0,1/\lambda_1,\ldots,1/\lambda_{N-1})$.

But before we try to calculate that let's test some cases. Set $N=4$. Also sprach Mathematica: $$(1+4\nu^2)M(4,\nu)^{-1}= \left(\begin{array}{cccc} 1+2\nu^2&-\nu&2\nu^2&\nu\\ \nu&1+2\nu^2&-\nu&2\nu^2\\ 2\nu^2&\nu&1+2\nu^2&-\nu\\ -\nu&2\nu^2&\nu&1+2\nu^2 \end{array}\right)$$ Both $\nu$ and $-\nu$ appear as coefficients, so I don't see a way of making all the entries positive here.

• In the $N=5$ case we get more complicated formulas. Assuming that $\nu$ is small in comparison to $1$, the leading term appears with both signs. The problem persists. Jun 24 '15 at 10:25
• This Matrix actually arises while proving the stability of the BTCS scheme for the Linear Hyperbolic equation $u_t + a u_x = 0$, where $u_x$ denotes the partial derivative of the function $u(x,t)$ wrt $x$. As this is an implicit method, the relation between the terms can be shown to be $M u^{n+1} = u^{n}$ where M is the matrix given above. In the $L_2$ norm, the numerical method is actually stable. So, the sum of each of the rows and each of the columns of inverse of this matrix should actually add upto 1 and additionally all the entries should be positive. Jun 24 '15 at 12:14
A quick observation: when the size $N$ of the matrix is even, $M^{-1}$ can never be entrywise positive.
As pointed out in the other answer, the eigenvalues of $M$ are $\lambda_k=1-2iv\sin\frac{2\pi k}{N}$, where $k=0,1,\ldots,\,N-1$. Therefore, when $N$ is even, $\lambda_0=\lambda_{N/2}=1$ is the only real eigenvalue of both $M$ and $M^{-1}$ and it has multiplicity $2$. However, by Perron-Frobenius theorem, if $M^{-1}$ is positive, it must possess a simple real eigenvalue (namely, the spectral radius $\rho(M^{-1})$).