3
$\begingroup$

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.

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

2 Answers 2

Reset to default
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ What about the columns that are linearly dependant, do they also have eigenvalue 1 or do they just don't count? $\endgroup$
    – WarreG
    Commented Jan 9, 2018 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$
    – QED
    Commented Jan 9, 2018 at 14:29
  • $\begingroup$ Yes, thank you very much! $\endgroup$
    – WarreG
    Commented Jan 9, 2018 at 14:32
1
$\begingroup$

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.

$\endgroup$
3
  • $\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
    Commented Jan 9, 2018 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.Γ.
    Commented Jan 9, 2018 at 14:42
  • $\begingroup$ Ah yes I see, thanks! $\endgroup$
    – WarreG
    Commented Jan 9, 2018 at 14:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .