Como todas las normas en $M_n(\mathbb C)$ son equivalentes, se puede utilizar cualquier norma que se nos plazca. Voy a utilizar la norma $\|a\|=\sum_{i,j}|a_{ij}|$.
Deje $p_1$ ser el selfadjoint de la matriz dada por
$$
(p_1)_{ij}=\begin{cases}p_{ij},&\mbox{ if }i< j\\ \\ \mbox{Re}\,p_{jj},&\,\mbox{ if }i=j \\ \\ \overline{p_{ji}},&\mbox{ if }i>j\end{casos}
$$
Tenga en cuenta que $p_1$ es selfadjoint, $\|p_1-p\|\leq\|p^*-p\|<\varepsilon$, e $$\|p_1^2-p_1\|\leq\|p_1^2-p_1p\|+\|p_1p-p^2\|+\|p^2-p\|+\|p-p_1\|\leq(\|p_1\|+\|p\|+2)\,\varepsilon=(2+\|p\|)\,\varepsilon.$$
También, de $\|p-p^2\|<\varepsilon$ tenemos
$$
\|p\|^2\leq\|p\|+\varepsilon,
$$
lo que muestra que $\|p\|\leq1/2+\sqrt{\varepsilon+1/4}\leq 1+\sqrt\varepsilon$. Así que nuestra primera estimación se convierte en
$$
\|p_1^2-p_1\|\leq(3+\sqrt\varepsilon)\,\varepsilon.
$$
Desde $p_1$ es selfadjoint, podemos diagonalize: $p_1=vdv^*$, $v$ unitario e $d$ diagonal con entradas real. Desde $v$ es unitaria, $\|v\|\leq n^2$ (usando sólo que todas las entradas en $v$ son de valor absoluto en la mayoría) y así
$$
\|d^2-d\|=\|v^*(p_1^2-p_1)v\|\leq n^4\|p_1^2-p_1\|\leq n^4(3+\sqrt\varepsilon)\,\varepsilon.
$$
Esto demuestra que cada autovalor de a $p_1$ es cerca de $0$ o cerca de $1$ al $\varepsilon$ es pequeña. Concretamente,
$$
\frac{1-\sqrt{1+4n^4(3+\sqrt\varepsilon)\,\varepsilon}}2\leq|d_{jj}|\leq\frac{1-\sqrt{1-4n^4(3+\sqrt\varepsilon)\,\varepsilon}}2
$$
o
$$
\frac{1-\sqrt{1+4n^4(3+\sqrt\varepsilon)\,\varepsilon}}2\leq|1-d_{jj}|\leq\frac{1-\sqrt{1-4n^4(3+\sqrt\varepsilon)\,\varepsilon}}2.
$$
El uso de que si $a<|d|<b$ $b>0$, $a<0$ a continuación,$|d|<b-a$, obtenemos
$$
|d_{jj}|\leq8n^4(3+\sqrt\varepsilon)\,\varepsilon,\ \mbox{ o }|1-d_{jj}|\leq8n^4(3+\sqrt\varepsilon)\,\varepsilon
$$
(el uso de ese $\sqrt{1+a}-\sqrt{1-a}\leq2a$$a>0$).
Así que vamos a $e$ ser una matriz diagonal con $e_{jj}=0$ si $|d_{jj}|\leq1/2$, $e_{jj}=1$ si $|d_{jj}|>1/2$. Deje $q=vev^*$. A continuación, $q$ es un selfadjoint de proyección y
$$
\|p-p\|\leq\|p-p_1\|+\|p_1-p\|\leq n^4\|e-d\|+\varepsilon\leq n^4\,n8n^4(3+\sqrt\varepsilon)\,\varepsilon=8n^6(3+\sqrt\varepsilon)\,\varepsilon.
$$
Finalmente, para responder a la pregunta: si un límite prescrito en $\varepsilon$ (que es básicamente la misma que la prescripción de un obligado en la norma de $p$), el $k$ puede ser encontrado. Por ejemplo, si $\varepsilon\leq1$, entonces podemos tomar $k=8n^6\times4=32n^6$.