$\mathbf{A}^T = p(\mathbf{A})$, prove that $\mathbf{A}$ is invertible Let $\mathbf{A}$ be a square matrix defined over a field $\mathbb{R}$. It is known that $\mathbf{A}^\text{T} = p(\mathbf{A})$, where $p(\mathbf{A})$ is a polynomial with a constant coefficient $a_0 \neq 0$. 


*

*Prove that $\mathbf{A}$ is invertible. 

*Is it true that for every operator $\mathbb{\phi}: \mathbb{R}^n\rightarrow\mathbb{R}^n$ there exists some polynomial $p(x)$ and the basis for which the matrix $\phi$ satisfies the condition of $\mathbf{A}^\text{T} = p(\mathbf{A})$?


Solution
I.
By the definition of $\mathbf{A}$: $$\mathbf{A}^t = P(\mathbf{A}) = a_n \cdot \mathbf{A}^n + \cdots + a_1 \cdot \mathbf{A} + a_0 \cdot \mathbf{I}$$
Consider
$$\mathbf{A}^t \cdot \mathbf{A} = a_n \cdot \mathbf{A}^n \cdot \mathbf{A} + \cdots + a_1 \cdot \mathbf{A} \cdot \mathbf{A} + a_0 \cdot \mathbf{I} \cdot \mathbf{A} \\ = a_n \cdot \mathbf{A}^{n + 1} + \cdots + a_1 \cdot \mathbf{A}^2 + a_0 \cdot \mathbf{A}$$
$$\mathbf{A} \cdot \mathbf{A}^t = a_n \cdot \mathbf{A} \cdot \mathbf{A}^n + \cdots + a_1 \cdot \mathbf{A} \cdot \mathbf{A} + a_0 \cdot \mathbf{A} \cdot I \\ = a_n \cdot \mathbf{A}^{n + 1} + \cdots + a_1 \cdot \mathbf{A}^2 + a_0 \cdot \mathbf{A}$$
hence, $\mathbf{A}^t \cdot \mathbf{A} = \mathbf{A} \cdot \mathbf{A}^t$. Therefore, the matrix $\mathbf{A}$ is normal, which assumes $\text{ker}(\mathbf{A}) = \text{ker}(\mathbf{A^t})$. Assume that $\mathbf{A}$ is not invertible, then its kernel is non-trivial. Take non-zero $v$ from $\text{ker}(\mathbf{A})$:
$$\mathbf{A}^t \cdot v = a_n \cdot \mathbf{A}^n \cdot v + \cdots + a_1 \cdot \mathbf{A} \cdot v + a_0 \cdot \mathbf{I} \cdot v \\ \mathbf{A}^t \cdot v = 0 + \cdots + 0 + a_0 \cdot v = a_0 \cdot v$$
As per definition, $a_0 \neq 0$, so $a_0 \cdot v \neq 0$, and it follows that $\mathbf{A}^t \cdot v \neq 0$. However, the condition $\text{ker}(\mathbf{A})=\text{ker}(\mathbf{A^t})$ implies that $\mathbf{A}^t \cdot v = 0$. We have a contradiction, hence $\mathbf{A}$ is invertible.
II.
It was proven that $\mathbf{A}$ is normal if its transpose can be represented by a polynomial. But normality is independent of the basis chosen, so the second statement would mean that every operator is normal, which is not the case.
Any mistakes, improvements?
 A: Your proof for part 1 is perfect. 
For part 2, I assume that the question should be as follows:

Is it true that for every operator $\phi: \mathbb{R}^n\rightarrow\mathbb{R}^n$, there exists some polynomial $p(x)$ and a basis for which the matrix of $\phi$ relative to this basis satisfies the condition of $A^\top = p(A)$?

First, to correct the answer you gave, it is not true that normality is independent of the basis chosen: If you apply a non-unitary change of basis to a normal matrix, then the resulting matrix might not be normal. For instance, note that if we take
$$
A = \pmatrix{0&2\\2&0}, \quad S = \pmatrix{2&0\\0&1}, 
$$
then $A$ is normal but $SAS^{-1}$ is not.
One way to answer the question is to give an example of an operator for which the condition cannot hold. Consider in particular the operator $\phi(x) = Mx$ with
$$
M = \pmatrix{0&1\\0&0}.
$$
$\phi$ fails to be diagonalizable and therefore cannot be normal relative to any choice of basis. Thus, it cannot be the case that the matrix $A$ of $\phi$ satisfies $A^\top = p(A)$.
A: For the first question, suppose $Ax=0$. Then
$$
0=(Ax)^Tx=x^TA^Tx=x^T\left(p(A)x\right)=a_0x^Tx=a_0\|x\|_2^2.
$$
Therefore $x$ must be zero and $A$ is invertible.
