2

Suppose I have two matrices

$$A = \begin{bmatrix} 0 & 1 \\ a_2 & a_1\end{bmatrix}$$ $$B = \begin{bmatrix} 0 & 1 \end{bmatrix}$$

Then $AB^T = \begin{bmatrix} 1 \\ a_1\end{bmatrix}$, the last term is $a_1$

Now I expand matrix $A$ and $B$ a little bit to get

$$A = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ a_3 & a_2 & a_1\end{bmatrix}$$ $$B = \begin{bmatrix} 0 & 0 & 1 \end{bmatrix}$$

Then I find $AB^T = \begin{bmatrix} 0 \\ 1 \\ a_1\end{bmatrix}$, the last term is $a_1$, furthermore $A^2B^T = \begin{bmatrix} 1 \\ a_1 \\ a_1^2 + a_2 \end{bmatrix}$, the last term is $a_1^2 + a_2$, neato!

Finally let's define our matrix to be: $$A = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ a_4 & a_3 & a_2 & a_1\end{bmatrix}$$ $$B = \begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix}$$

As before, I find $AB^T = \begin{bmatrix} 0 \\ 0 \\ 1 \\ a_1\end{bmatrix}$, the last term is $a_1$, furthermore $A^2B^T = \begin{bmatrix} 0 \\ 1 \\ a_1 \\ a_1^2 + a_2 \end{bmatrix}$, the last term is $a_1^2 + a_2$

Curiously, I can compute $A^3B^T$ and obtain $\begin{bmatrix} 1 \\ a_1 \\ a_1^2 + a_2 \\ a_3 + a_2a_1 + a_1(a_1^2+a_2) \end{bmatrix}$

Now suppose A and B are both N dimensional matrices.

Is there a closed form solution for the n by nth value of the product $A^{n-1}B^T$?

Note: $A$ and $B$ pair are what known as the canonical controllable form

Victor
  • 8,372
Fraïssé
  • 11,275

2 Answers2

3

Let $(A^{n-1})_{n\times n}\times (B^T)_{n\times 1}=C_{n\times 1}$ $\qquad \qquad (C=[c_1 \ldots c_n]^T)$

The set $C$ can be defined recursively as follows: \begin{align} c_1&=1 \\ c_k&=\sum_{i=1}^{k-1}a_ic_{k-i} \qquad (2\leq k \leq n)\end{align}

To see why, first note that since all elements of $B$ except the last one are $0$, only the last column of $A^{n-1}$ takes part in forming $C$. So we need to focus on how this column evolves starting at $A^1$.

Also notice the special structure of $A$. Informally speaking, when a matrix of this kind is multiplied by another matrix $D$, it "pushes" the rows of $D$ one level up: (The last row is hidden to illustrate the point more clearly) $$ \begin{bmatrix} 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ \alpha&\beta&\gamma&\delta \end{bmatrix} \begin{bmatrix} a&b&c&d\\ e&f&g&h\\ i&j&k&l\\ m&n&o&p \end{bmatrix} = \begin{bmatrix} e&f&g&h\\ i&j&k&l\\ m&n&o&p\\ & & & \end{bmatrix} $$

$$ \Bigg(\begin{bmatrix} 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ \alpha&\beta&\gamma&\delta \end{bmatrix}\Bigg)^2 \begin{bmatrix} a&b&c&d\\ e&f&g&h\\ i&j&k&l\\ m&n&o&p \end{bmatrix} = \begin{bmatrix} i&j&k&l\\ m&n&o&p\\ & & &\\ &&& \end{bmatrix} $$

It follows from these two observation that we just need to find out how the last element of the last column of $A$ evolves. Now it should be straightforward to see why $C$ is defined by the recursive definition mentioned above. You should be able to construct the formal proof (if it is necessary), though it is tedious and takes time.

LoMaPh
  • 1,361
1

It's more helpful to write $\begin{bmatrix} 1 \\ a_1 \\ a_2 + a_1^2 \\ a_3 + 2 a_1a_2 + a_1^3 \end{bmatrix}$.

The next one is $\begin{bmatrix} 1 \\ a_1 \\ a_2 + a_1^2 \\ a_3 + 2 a_1a_2 + a_1^3\\a_4+2a_1a_3+3 a_1^2a_2 +a_2^2+a_1^4 \end{bmatrix}$.

The next one is $\begin{bmatrix} 1 \\ a_1 \\ a_2 + a_1^2 \\ a_3 + 2 a_1a_2 + a_1^3\\a_4+2a_1a_3+3 a_1^2a_2 +a_2^2+a_1^4\\a_5+2a_1a_4+2a_2a_3+3 a_1a_2^2+3a_3a_1^2 +4a_1^3a_2+a_1^5 \end{bmatrix}$.

Each term is linked to a partition of n.

So for example, one of the partitions of 5 is 2+2+1. Therefore one of the terms is the product of $a_2$ and $a_2$ and $a_1$, which is $a_1a_2^2$.

Each term has a coefficient that is equal to the number of $a_i$ that are multiplied together to make that term.

So for example the term above is the product of three values $a_2$ and $a_2$ and $a_1$, so the coefficient is 3.

The only exception to this coefficient rule is the last term, which is always $a_1^n$.

Partitions of 6 are:

6: $a_6$

1+5: $2a_1a_5$

2+4: $2a_2a_4$

3+3: $2a_3^2$

1+1+4: $3a_1^2a_4$

1+2+3: $3a_1a_2a_3$

2+2+2: $3a_2^3$

1+1+1+3: $4a_1^3a_3$

1+1+2+2: $4a_1^2a_2^2$

1+1+1+1+2: $5a_1^4a_2$

1+1+1+1+1+1: $a_1^6$

tomi
  • 9,594