# if P = NP then N has an eigenspace that is at least rank(P)-dimensional.

So $N,P \in \mathbb{R}^{n x n}$ with $P \neq O$. I have to prove that if $$P = NP,$$ $N$ has an eigenspace that is at least rank($P$)-dimensional.

I haven't made a lot of progress because I don't know how to start proving this. If anyone has a hint to push me in the right direction, that would be appreciated.

• I find $P=NP$ some false advertising for this question. Commented Jan 9, 2018 at 14:02
• I'm not looking for attention or points, I just want this proof solved! It is what it is! From the rest of the title it's clear that it isn't THE P=NP problem. Commented Jan 9, 2018 at 14:31

$P=NP\implies$ Each column of $P$ is an eigenvector of $N$ corresponding to the eigenvalue $1$.

• What about the columns that are linearly dependant, do they also have eigenvalue 1 or do they just don't count? Commented Jan 9, 2018 at 14:27
• Yep they also have eigenvalue $1$. Because if $p_k$ is $k$-th column of $P$, then $Np_k=p_k$. Now do you get it?
– QED
Commented Jan 9, 2018 at 14:29
• Yes, thank you very much! Commented Jan 9, 2018 at 14:32

Partition the matrix $P$ into columns $$p=\begin{bmatrix}p_1 & p_2 & \ldots & p_n\end{bmatrix}$$ and rewrite $P=NP$ in terms of the columns $p_k$. You will see the eigenvectors. Then use the definition of rank in terms of linear independent columns.

• I see now that all columns of $P$ are eigenvectors with eigenvalue $1$. Let's say there are $k$ independant columns $k \leqslant n$ then the eigenspace has dimension $k$ and so is the $rank(A)$? Is that a good reasoning? Commented Jan 9, 2018 at 14:22
• @WarreG If rank$(P)=k$ then there are $k$ linearly independent columns, hence, $k$ linearly independent eigenvectors with $\lambda=1$. However, it does not say that the eigenspace has the dimension $k$, because it may exist more linearly independent eigenvectors with $\lambda=1$ that are not columns of $P$. But we know that the dimension of the eigenspace is at least $k$.
– A.Γ.
Commented Jan 9, 2018 at 14:42
• Ah yes I see, thanks! Commented Jan 9, 2018 at 14:49