Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a arbitrary $N \times N$ matrix $S$. I have an function of this matrix given by:

$$A = F(S) = 2S + P^{-1}S + 2SP + PSP$$

where $P$ is the a cyclic permutation matrix which when acting on the left of a matrix sends row $i$ to row $i-1$ (with $0 = N$). For example with $N=3$

$$P = \begin{pmatrix} 0&0&1 \\ 1&0&0 \\ 0&1&0 \end{pmatrix}.$$

Thus $P^N = I$. I want to invert the above equation to find $ S = F^{-1}(A) $ which I am sure can be done.

Does anyone have any suggestions for how to do this most effectively?

share|cite|improve this question
up vote 3 down vote accepted

Why are you "sure" that $F$ has an inverse? In fact, when $N=3$, $F$ has no inverse. To see this, note that $P^{-1}=P^2$ and $P^3=I$. So, if we put $S=P-I$, we have $$ \begin{eqnarray} F(S) &=& 2S + P^{-1}S + 2SP + PSP\\ &=& 2(P-I) + P^{-1}(P-I) + 2(P-I)P + P(P-I)P\\ &=& (2P-2I) + (I-P^{-1}) + (2P^2-2P) + (P^3-P^2)\\ &=& (2P-2I) + (I-P^2) + (2P^2-2P) + (I-P^2) = 0. \end{eqnarray} $$ So $F(S)=0$ for some nonzero $S$. Hence $F$ has no inverse.

share|cite|improve this answer
yes I have just come to that as well... in fact I now think that it will be non-invertible for any $N$... – Kyle Sep 9 '11 at 5:02
Not exactly. For even $N$, $F$ has no inverse because $F(uu^T)=0$ when $u^T=(1,-1,1,-1,\ldots,1,-1)$. For odd $N$ between 3 and 27, $F$ is non-invertible only when $N=3,9$, and I have no idea which odd $N$ in general will give rise to an invertible $F$. – user1551 Sep 9 '11 at 5:58
I understand now why my intuition was wrong here, the domain I am interested in is the positive matrices $S_{ij}>0$. – Kyle Sep 9 '11 at 7:00
For even $N$, restricting $S$ to positive definite matrices does not change the conclusion. In my above comment, we have $F(uu^T)=0$. The matrix $uu^T$ is Hermitian but not positive definite. However, for any positive definite matrix $S$, the sum $S+\alpha uu^T$ is positive definite when $\alpha$ is sufficiently small. Since $F(S+\alpha uu^T)=F(S)$, $F$ is still non-invertible. – user1551 Sep 9 '11 at 9:30
I am interested in the positive (non-negative) matrices not the positive definite ones, however I believe that doesn't change the conclusions of the above comment as (like you said) for positive $S$, $S + \alpha uu^{T}$ will still be positive for sufficiently small $\alpha$. – Kyle Sep 9 '11 at 22:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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