I would like to show that if $A$ is a positive semidefinite matrix and $P$ is a permutation matrix then $P^TAP$ is also PSD.

Question

bobo-i-bo · Answer

According to wikipedia, a matrix M being positive-definite is equivalent to M having all positive eigenvalues. So assuming that PSD is equivalent to non-negative eigenvalues, then it's very obvious that $P^TAP$ is also PSD.

bobo-i-bo · Answer

My assumption is correct :) PSD matrix is equivalent to a having only non-negative eigenvalues.

michele_laino · Answer

here is my reasoning:
I consider a permutation Matrix $P$, so, from the general theory on matrices and determinants, we have:
$$\det P = {\left( { - 1} \right)^n}\left( {\det {I_n}} \right) = {\left( { - 1} \right)^n},\quad {P^T}P = {I_n}$$
wherein $I_n$ is the identity Matrix, and $n$ is the dimension, over the set of real numbers, of the involved vector space.
Next we have:
$$\begin{gathered}
  \det \left( {{P^T}AP - \lambda I} \right) = \det \left( {{P^T}AP - {P^T}\lambda IP} \right) =  \hfill \
   \hfill \
   = \det \left( {{P^T}\left( {A - \lambda I} \right)P} \right) = \left( {\det {P^T}} \right)\left\{ {\det \left( {A - \lambda I} \right)} \right\}\det P =  \hfill \
   \hfill \
   = {\left( {{{\left( { - 1} \right)}^n}} \right)^2}\left\{ {\det \left( {A - \lambda I} \right)} \right\} = \det \left( {A - \lambda I} \right) \hfill \ 
\end{gathered} $$
namely the matrices $P^TAP$ and $A$ have the same characteristic polynomial, and then have the same eigenvalues, so if $A$ is positive semidefinite, als $P^TAP$ is positive semidefinite

michele_laino · Answer

wherein the eponent $n$ in $(-1)^n$ is the number of swaps of columns starting from the identity matrix