Rational Matrix Powers with certain rowsum vector

Question

Given a set of $n$ vectors in a $n$-dimensional vector space $\{u_1, u_2,...,u_n\}$ I am interested in a method to get a $n \times n$ matrix $A$ whose first $n$ powers have each of those vectors as rowsum which means that for $1\leq k\leq n$ the matrix $A$ verifies

$$A^k \begin{align} \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \\ 1 \end{bmatrix} \end{align} = u_k.$$

Answer 1

This isn't always guaranteed. You need additional constraints on what your vectors can be.

Counterexample Consider the vectors $$ u_1 \;\; =\;\; \left [ \begin{array}{c} 1\\1\\ \end{array} \right ] \hspace{3pc} u_2 \;\; =\;\; \left [\begin{array}{c} -1 \\ 1 \\ \end{array} \right ]. $$

Then the we want a $2\times 2$ matrix $A$ that satisfies $Au_1 = u_1$ and $A^2u_1 = u_2$. By the first constraint we want that $$ \left [\begin{array}{cc} a & b \\ c & d \\ \end{array} \right ]\left [ \begin{array}{c} 1\\1\\ \end{array} \right ] \;\; =\;\; \left [ \begin{array}{c} a+b \\ c+d \\ \end{array} \right ] \;\; =\;\; \left [ \begin{array}{c} 1\\1\\ \end{array} \right ]. $$

When we try to find $A^2$ to obtain our second vector we find that \begin{eqnarray*} \left [\begin{array}{cc} a & b \\ c & d \\ \end{array} \right ]\left [\begin{array}{cc} a & b \\ c & d \\ \end{array} \right ]\left [ \begin{array}{c} 1\\1\\ \end{array} \right ] & = & \left [\begin{array}{cc} a^2 + bc & b(a+d) \\ c(a+d) & d^2 + bc \\ \end{array} \right ]\left [ \begin{array}{c} 1\\1\\ \end{array} \right ] \\ & = & \left [ \begin{array}{c} a^2 + b(a+c+d) \\ d^2 + c(a+b+d) \\ \end{array} \right ] \\ & = & \left [ \begin{array}{c} a^2 + ab + b \\ d^2 + cd+c \\ \end{array} \right ] \\ & = & \left [ \begin{array}{c} a+b \\ c+d \\ \end{array} \right ]\;\; =\;\;\left [ \begin{array}{c} 1\\1\\ \end{array} \right ]. \end{eqnarray*}

Therefore no matrix $A$ exists where $Au_1 = u_1$ and $A^2u_1 = u_2$.

Answer 2

Let $u_0=[1,\cdots,1]^T$. Your required condition implies that $u_n$ is a linear combination of $u_0,\cdots,u_{n-1}$.

A better question is :

$\textbf{Proposition}$. Let $u_1,\cdots,u_{n-1},u_n$ be s.t. $u_0,u_1,\cdots,u_{n-1}$ is a basis of $K^n$.

Then, show that there is a unique matrix $A$ s.t. $A^ku_0=u_k,1\leq k\leq n$.

$\textbf{Proof}$. Note that $Au_0=u_1,Au_1=u_2,\cdots,Au_{n-1}=u_n$ and we may write $u_n=\sum_{0\leq i\leq n-1}a_iu_i$.

Let $P$ be the matrix of change of basis $(e_i)_i\rightarrow (u_j)_{0\leq j\leq n-1}$. Then $P^{-1}AP$ is THE companion matrix $C$ s.t. its $n^{th}$ column is $[a_0,\cdots,a_{n-1}]^T$. $\square$

EDIT. Answer to the OP

$A=PCP^{-1}$ where $c_{i,j}=0$ except $c_{i+1,i}=1$ and $c_{i,n}=a_{i-1}$.