# Quick way of showing an $n\times n$ Jordan block associated to $1$ is similar to the companion matrix of $(x-1)^n$

Is there a quick, clean way of proving that the $n\times n$ Jordan block with $1$'s on the diagonal and the Frobenius companion matrix corresponding to the polynomial $(x-1)^n$ are similar matrices?

Apparently, the (triangular) Pascal matrix is the required similarity transformation, but I'm stuck showing why it works (mostly in constructing the sums implied by the needed matrix multiplications). Or better yet, can this assertion be proven without explicitly invoking the Pascal matrix?

-

The number of blocks of size at least $k$ corresponding to $\lambda$ in the Jordan canonical form is equal to nullity of $(A-\lambda I)^k$ minus the nullity of $(A-\lambda I)^{k-1}$.

The number of companion blocks in the rational canonical form corresponding to powers $p(t)^m$ with $m\geq k$ (where $p(t)$ is an irreducible factor of the minimal polynomial) is likewise equal to the nullity of $p(A)^m$ minus the nullity of $p(A)^{m-1}$.

If the minimal polynomial of $A$ splits, then the irreducible factors of the minimal polynomial are all of the form $(x-\lambda)$, so the number of companion blocks correspond to powers $(x-\lambda)^m$ with $m\geq k$ is exactly equal to the number of Jordan blocks in the Jordan canonical form of size at least $k$ and corresponding to $\lambda$.

In particular, the companion matrix of $(x-1)^n$ is already in Rational Canonical form, and has a single block corresponding to the power $(x-1)^n$; its Jordan canonical form will therefore have exactly one block, corresponding to $\lambda=1$, and of size $n\times n$. Since any matrix is similar to its Jordan canonical form, it follows that the $n\times n$ Jordan block matrix with $1$s in the diagonal is similar to the companion matrix of $(x-1)^n$.

To see why the Pascal matrix realizes the similarity, let $A$ be the $n\times n$ matrix with $1$s in the diagonal and $1$s directly above (i.e., a single $n\times n$ Jordan block associated to $1$). Then the standard ordered basis $[\mathbf{e}_1,\ldots,\mathbf{e}_n]$ is a Jordan canonical basis for $A$, and we have $A\mathbf{e}_1=\mathbf{e}_1$, $A\mathbf{e}_k = \mathbf{e}_{k-1}+\mathbf{e}_k$, $k=2,\ldots, n$.
To get a rational canonical basis, we need a vector $\mathbf{v}$ that lies in the kernel of $(A-I)^n$, but not in the kernel of $(A-I)^{n-1}$; then the rational canonical basis will be $[\mathbf{v},A\mathbf{v},A^2\mathbf{v},\ldots,A^{n-1}\mathbf{v}]$. It is not hard to verify that $(A-I)^k$ is a matrix that has $1$s in the $k$th diagonal above the main diagonal and $0$s elsewhere. So $(A-I)^n$ is the zero matrix, and $(A-I)^{n-1}$ is a matrix whose only nonzero entry is a $1$ in the $(1,n)$ entry. Thus, we can take $\mathbf{v}=\mathbf{e}_n$. So the rational canonical ordered basis is $[\mathbf{e}_n,A\mathbf{e}_n,\ldots,A^{n-1}\mathbf{e}_{n-1}]$, or explicitly: \begin{align*} &\phantom{=} \mathbf{e}_n\\ A\mathbf{e}_n &= \mathbf{e}_{n-1}+\mathbf{e}_n\\ A^2\mathbf{e}_n &= \mathbf{e}_{n-2} + 2\mathbf{e}_{n-1}+\mathbf{e}_n\\ A^3\mathbf{e}_n &= \mathbf{e}_{n-3}+3\mathbf{e}_{n-2}+3\mathbf{e}_{n-1}+\mathbf{e}_n\\ &\vdots\\ A^{n-1}\mathbf{e}_n &= \binom{n-1}{0}\mathbf{e}_1 + \binom{n-1}{1}\mathbf{e}_{2} + \binom{n-1}{2}\mathbf{e}_3 + \cdots + \binom{n-1}{n-2}\mathbf{e}_{n-1} + \binom{n-1}{n-1}\mathbf{e}_n \end{align*} The change-of-basis matrix from the rational canonical basis to the standard basis is therefore: $$Q=\left(\begin{array}{ccccc} 0 & 0 &\cdots & 0 &\binom{n-1}{n-1}\\ 0 & 0 & \cdots &\binom{n-2}{n-2} & \binom{n-1}{n-2}\\ 0 & 0& \cdots & \binom{n-2}{n-3} & \binom{n-1}{n-3}\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & \binom{1}{1} & \cdots & \binom{n-2}{1} & \binom{n-1}{1}\\ 1 & \binom{1}{0} & \cdots & \binom{n-2}{0} & \binom{n-1}{0} \end{array}\right)$$ so $Q^{-1}AQ$ will be the companion matrix of $(x-1)^n$.
Added${}^{\mathbf{2}}$. Note that the argument in the first paragraph shows that an $n\times n$ Jordan block associated to $\lambda$ is similar to the companion matrix of $(x-\lambda)^n$, for any $\lambda$, not just for $n=1$; and more generally, if we let $J(\lambda,k)$ denote a $k\times k$ Jordan block associated to $\lambda$; $C(p(x))$ denote the companion matrix of $p(x)$; and $B_1\oplus B_2\oplus \cdots \oplus B_n$, with $B_i$ square matrices, denote the block-diagonal matrix with diagonal blocks equal to $B_1$, $B_2,\ldots,B_n$, then the matrix $$J(\lambda_1,k_1)\oplus J(\lambda_2,k_2)\oplus\cdots\oplus J(\lambda_m,k_m)$$ is similar to the matrix $$C((x-\lambda_1)^{k_1}) \oplus C((x-\lambda_2)^{k_2})\oplus\cdots\oplus C((x-\lambda_m)^{k_m}),$$ with your question being the case $m=1$, $\lambda_1=1$, $k_1=n$.
@Joost: I've added a derivation; it may not be exactly the "Pascal matrix" you are thinking about, but I trust it will be clear. The key is that $\mathbf{e}_n$ will generate a rational canonical basis for $A$. –  Arturo Magidin Jun 29 '11 at 16:33