Bairaxx

Answered

2022-10-25

Matrix representations and polynomials

I just investigated the following matrix and some of its lower powers:

$$\mathbf{M}=\left[\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 0& 0\\ 1& 1& 1& 0\\ 1& 1& 1& 1\end{array}\right],{\mathbf{M}}^{2}=\left[\begin{array}{cccc}1& 0& 0& 0\\ 2& 1& 0& 0\\ 3& 2& 1& 0\\ 4& 3& 2& 1\end{array}\right],\phantom{\rule{0ex}{0ex}}{\mathbf{M}}^{3}=\left[\begin{array}{cccc}1& 0& 0& 0\\ 3& 1& 0& 0\\ 6& 3& 1& 0\\ 10& 6& 3& 1\end{array}\right],{\mathbf{M}}^{4}=\left[\begin{array}{cccc}1& 0& 0& 0\\ 4& 1& 0& 0\\ 10& 4& 1& 0\\ 20& 10& 4& 1\end{array}\right]$$

As a function of the exponents, indices (1,1) seem to be constant 1, (2,1) seem to be linear function, (3,1) seem to be arithmetic sum and the fourth one seems to be sums of arithmetic sums. I have some faint memory that these should be polynomials of increasing order (well I know it for sure up to the arithmetic sum), but I can't seem to remember what they were called or how to calculate them. Does it make sense to do polynomial regression or is that uneccessary? This is following the train of thought from matrix representation of generating element for parabola, maybe you can see what I'm jabbing away at.

So the question is: is there an easy way to linearly combine the first columns of these matrices to generate the first 4 monomials? I can always do a linear regression with monomial basis functions, but that would be a little silly if this is already a well known way to do it.

Want to know more about Two-wayTables?

Answer & Explanation

toliwask

Expert

2022-10-26Added 15 answers

Step 1

Maybe not exactly what you are asking, but notice that your matrix is lower triangular, and can be written as $M=I+N$, with I the identity and

$$N=\left(\begin{array}{cccc}0& 0& 0& 0\\ 1& 0& 0& 0\\ 1& 1& 0& 0\\ 1& 1& 1& 0\end{array}\right).$$

Step 2

N is nihilpotent, ${N}^{4}=0$ and (obviously) commutes with I, hence

$$(I+N{)}^{n}=\sum _{i=0}^{n}{\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )}{N}^{i}=\sum _{i=0}^{3}{\textstyle (}\genfrac{}{}{0ex}{}{n}{i}{\textstyle )}{N}^{i},$$

hence you only need N, ${N}^{2}$ and ${N}^{3}$ to compute any power of M.

Deja Bradshaw

Expert

2022-10-27Added 4 answers

Step 1

We can simplify GFR's approach and go further: let X be the matrix

$$\left(\begin{array}{cccc}0& 0& 0& 0\\ 1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\end{array}\right)$$

Then

$$M=I+X+{X}^{2}+{X}^{3}=\sum _{k=0}^{\mathrm{\infty}}{X}^{k}=(I-X{)}^{-1}$$

Step 2

Consequently,

$${M}^{n}=(I-X{)}^{-n}=\sum _{k=0}^{\mathrm{\infty}}{\textstyle (}\genfrac{}{}{0ex}{}{-n}{k}{\textstyle )}(-X{)}^{k}=\sum _{k=0}^{\mathrm{\infty}}{\textstyle (}\genfrac{}{}{0ex}{}{n+k-1}{k}{\textstyle )}{X}^{k}=\sum _{k=0}^{3}{\textstyle (}\genfrac{}{}{0ex}{}{n+k-1}{k}{\textstyle )}{X}^{k}$$

where I've used the generalized Binomial theorem and the formula for binomial coefficients to negative integers.

Most Popular Questions