# Inverting Matrix Equations Y = F(X)

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?

-

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