Which change of basis matrix makes a companion matrix similar to its transpose? I know that a companion matrix is similar to its transpose e.g by Smith normal form. When the characteristic polynomial splits, companion matrices become Jordan blocks. A Jordan block is similar to its transpose via the matrix comprised of 1's on the "opposite diagonal" and zeros elsewhere.
This leads me to wonder: Is there a simple description of the matrix which exhibits a companion matrix as similar to its transpose?
 A: Let $\psi$ be a monic poynomial of degree $d$ and let $V_\psi$ denote the vector space of polynomials modulo $\psi$, i.e., $\mathbb{F}[t]/(\psi)$. Multiplication by $t$ is a linear operator on this space, relative to the basis $1,t,\ldots,t^{d-1}$ it is represented by a companion matrix, $C_\psi$ say. Now if
\[
\psi(z) =t^d+a_1t^{d-1}+\cdots+a_d,
\]
we define polynomials $\psi_1,\ldots,\psi_d$ by
\[
\psi_i(z) :=t^{d-i}+a_1t^{d-i-1}+\cdots+a_{d-i}.
\]
These polynomials can also be defined by the initial condition
$\psi_d(z)=1$ and the backwards recurrence
\[
\psi_{i-1}(z) =z\psi_i(z)+a_{d-i+1}.
\]
Since $\psi_i(z)$ is monic of degree $d-i$, we see that these polynomials form a basis for $V_\psi$, sometimes called the control basis.
Suppose $v\in V_\psi$.  Then the vectors
\[
\psi_1(t)v,\ldots,\psi_d(t)v
\]
form a basis for $V_\psi$. It follows that
$$
 t\psi_i(t)v=\begin{cases}
 -a_dv,& \mathrm{if}\ i=1;\\
 \psi_{i-1}(t)v-a_{d+1-i}v,& \mathrm{if}\ 2\le i\le d.
    \end{cases}
$$
From this we see that the matrix representing $t$ with respect to the control basis is $C_\psi^T$, the transpose of the companion matrix of $\psi$. In conclusion, if you get your bases in the right order and
$$
Q = \begin{pmatrix}
    a_{d-1}&a_{d-2}&\dots&a_1&1\\
    a_{d-2}&a_{d-3}&&1&0\\
    \vdots&&&&\vdots\\
    a_1&1&&&0\\
    1&0&\dots&&0
  \end{pmatrix},
$$
then $Q^{-1}C_\psi Q$. It is interesting that $Q$ is symmetric.
This topic is treated at some length in Paul A. Fuhrmann ``A Polynomial Approach to Linear Algebra'' (which is where I learnt it).
