4

I just investigated the following matrix and some of its lower powers: $${\bf M} = \left[\begin{array}{cccc} 1&0&0&0\\ 1&1&0&0\\ 1&1&1&0\\ 1&1&1&1 \end{array}\right] , {\bf 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], \\{\bf 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] , {\bf 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.

Community
  • 1
mathreadler
  • 25,824

3 Answers3

9

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 \begin{equation} N=\begin{pmatrix} 0&0&0&0\\ 1&0&0&0\\1&1&0&0\\1&1&1&0 \end{pmatrix}.\end{equation}

N is nihilpotent, $N^4=0$ and (obviously) commutes with $I$, hence \begin{equation} (I+N)^n=\sum_{i=0}^n \binom{n}{i} N^i=\sum_{i=0}^3 \binom{n}{i} N^i, \end{equation} hence you only need $N$, $N^2$ and $N^3$ to compute any power of $M$.

GFR
  • 5,401
5

These are diagonals of Pascal's Triangle.

Empy2
  • 50,853
  • I knew I had seen them somewhere! So that means I probably should be looking for nCr and combinatorics relations to polynomials. – mathreadler Jul 04 '15 at 11:52
1

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

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

Then

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

Consequently,

$$M^n = (I-X)^{-n} = \sum_{k=0}^{\infty} \binom{-n}{k} (-X)^k = \sum_{k=0}^{\infty} \binom{n+k-1}{k} X^k = \sum_{k=0}^{3} \binom{n+k-1}{k} X^k $$

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