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.

  • 13
    $\begingroup$ I find $P=NP$ some false advertising for this question. $\endgroup$ – Mathematician 42 Jan 9 '18 at 14:02
  • $\begingroup$ 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. $\endgroup$ – WarreG Jan 9 '18 at 14:31

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

| cite | improve this answer | |
  • $\begingroup$ What about the columns that are linearly dependant, do they also have eigenvalue 1 or do they just don't count? $\endgroup$ – WarreG Jan 9 '18 at 14:27
  • $\begingroup$ 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? $\endgroup$ – Abishanka Saha Jan 9 '18 at 14:29
  • $\begingroup$ Yes, thank you very much! $\endgroup$ – WarreG Jan 9 '18 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.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – WarreG Jan 9 '18 at 14:22
  • $\begingroup$ @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$. $\endgroup$ – A.Γ. Jan 9 '18 at 14:42
  • $\begingroup$ Ah yes I see, thanks! $\endgroup$ – WarreG Jan 9 '18 at 14:49

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.