$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 ?


2 Answers 2


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

Please check the question.

  • $\begingroup$ 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. $\endgroup$ Jun 24, 2015 at 10:25
  • $\begingroup$ 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. $\endgroup$
    – Mathnoob
    Jun 24, 2015 at 12:14
  • $\begingroup$ The BTCS scheme is nothing but the Backward Time Central Space scheme. $\endgroup$
    – Mathnoob
    Jun 24, 2015 at 12:16

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})$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.