Matrix representation of linear map in this basis I am very stuck with this problem and I need help. I have tried different approaches, but I still don't know how to find the representation of $\mathcal{A}$ with respect to this new basis. Here is the problem:

Consider a linear map $\mathcal{A} : (U, F)\to(U, F)$ where $U$ has finite dimension $n$. Assume
  there exists a vector $b\in U$ such that the collection $$\{b,\mathcal{A}(b),\mathcal{A} \circ \mathcal{A}(b), ... ,\mathcal{A}^{n-1}(b)\}$$ forms a basis for $U$. Derive the representation of $\mathcal{A}$ and $b$ with respect to this basis.

Thank you very much.
 A: To summarize the (excellent!) discussion in the comments, you know so far that the matrix representation of $A$ with respect to the given ordered basis takes the form
$$
    [A] = (e_2 \mid e_3 \mid \cdots \mid e_n \mid v )
$$
where $e_i$ is the column vector with $1$ in its $i$-th entry and $0$ elsewhere and $v$ is some yet-to-be-determined vector. In particular, we know that $v = (\alpha_0,\alpha_1,\ldots,\alpha_{n-1})^T$ where $\alpha_i \in F$ ($0\leq i \leq n-1$) satisfy
$$
    A^n(b) = \alpha_0 b + \alpha_1 A(b) + \ldots + \alpha_{n-1}A^{n-1}(b).
$$
Hence (as the wonderfully-named @Omnomnomnom alludes to in his comment) we can rearrange this to be of the form
$$
    A^n(b) - \alpha_{n-1}A^{n-1}(b) - \ldots - \alpha_0 b = 0
$$
Moreover, if $0 \leq k \leq n-1$ we can compute that
\begin{align*}
    A^n[A^k(b)] - &\alpha_{n-1}A^n-1[A^k(b)] - \ldots - \alpha_0 A^k(b)\\
    &= A^k[A^n(b) - \alpha_{n-1}A^{n-1}(b) - \ldots - \alpha_0 b] \\
    &= A^k(0) \\
    &= 0,
\end{align*}
and so we have $p(A) = 0$ for $p(x) = x^n - \alpha_{n-1}x^{n-1} - \ldots - \alpha_0$ (since we have just shown that $p(A)(w) = 0$ for all $w$ in a basis of $U$). Furthermore, if $q$ is a polynomial of degree less than $p$, then $p(A) \neq 0$ (why?). Hence you can conclude that $p(x)$ is the minimal polynomial of $A$. This gives you a way to describe the final column vector $v$ in $[A]$ more explicitly.
A: I'll expand on some of the ideas from the exchange in the comments. applying $A$ to the first element of the basis ${\cal B} := \{b, Ab, \ldots, A^{n - 1} b\}$ gives $Ab$, the second basis element, so the first column of the matrix representation $[A]$ of $A$ w.r.t. $\cal B$ is $$\pmatrix{0\\1\\0\\ \vdots\\0}.$$ We can see that an analogous argument shows that the $k$th column of the matrix (the representation in the basis of $A(A^{k - 1} b) = A^k b$) is just
$$\pmatrix{0\\ \vdots\\0\\1\\0\\ \vdots\\0},$$ where the $1$ is in the $(k + 1)$st row. This determines all of the columns except the last one, so our matrix has the form
$$\pmatrix{
0 & 0 & \cdots & 0 & \ast\\
1 & 0 & \cdots & 0 & \ast\\
0 & 1 & \cdots & 0 & \ast\\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 1 & \ast
} .$$
On the other hand, we see that we can fill in the last column freely and the transformation $A$ will still satisfy the given criteria---in other words, the criteria don't tell us anything about the last column.
We can still, however, interpret the last column: Since $\cal B$ is a basis, we can write $A(A^{n - 1} b) = A^n b$ uniquely as a linear combination of the basis elements, that is, there are unique coefficients $-c_0, \ldots, -c_{n - 1}$ such that
$$A^n b = -c_0 b - c_1 A b - \cdots c_{n - 1} A^{n - 1} b = -(c_0 I + c_1 A + \cdots c_{n - 1} A^{n - 1}) b ,$$ in which case we can write the matrix as
$$\pmatrix{
0 & 0 & \cdots & 0 & -c_0\\
1 & 0 & \cdots & 0 & -c_1\\
0 & 1 & \cdots & 0 & -c_2\\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 1 & -c_{n - 1}
} .$$
I've taken the unusual step of including negative signs in the coefficients so that we can rearrange the above equation to read
$$(A^n + c_{n - 1} A^{n - 1} + \cdots + c_1 A + c_0 I) b = 0,$$
or just $$p(A) b = 0,$$ where $$p(t) := t^n + c_{n - 1} t^{n - 1} + \cdots + c_1 t + c_0 .$$ Applying $p(A)$ to $A^k b$ for $0 < k \leq n - 1$ shows that, in fact $p(A) = 0$. We say that $A$ is the (Frobenius) companion matrix of $p$, and it enjoys numerous nice properties: For example, induction shows that $p$ is the characteristic polynomial of $A$ (which again guarantees that $p(A) = 0$). Such matrices play a critical role in the sometimes-useful Frobenius Normal Form.
