4

I have a finite upper triangular $n$ by $n$ matrix $A$ which has the following form:

$$ A = \begin{pmatrix} 1 & 1\over 2 & 1\over 3 & \cdots & 1\over n \\ 0 & 1\over 2 & 1\over 3 & \cdots & 1\over n \\ 0 & 0 & 1\over 3 & \cdots & 1\over n \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ 0 & 0 & 0 & \cdots& 1\over n \end{pmatrix}$$

Or alternatively $A =TH$, where $T$ is the all-ones upper $n$ by $n$ triangular matrix and $H$ is the first $n$ terms of the harmonic series on the diagonal.

I'm interested in diagonalizing this matrix, as I'm interested in understanding and computing $A^k$ (specifically the final column). Since all elements on the diagonal are distinct the eigenvalues are simply the first $n$ terms of the harmonic series.

Doing some numerical analysis using numpy gave fairly opaque numbers, however Mathematica produced very interesting eigenvectors. E.g. for $n = 5$ the matrix with the eigenvectors as columns is:

$$P = \begin{pmatrix} 1 & -1 & 1 & -1 & 1 \\ 0 & 1 & -2 & 3 & -4 \\ 0 & 0 & 1 & -3 & 6 \\ 0 & 0 & 0 & 1 & -4 \\ 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix}, P^{-1} = \begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 1 & 3 & 6 \\ 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} $$

This seems to be some alternating sign Pascal triangle. In fact, $P^{-1}$ seems the be the actual Pascal triangle! And indeed $PHP^{-1} = A$ (no PHP pun intended), for the cases I've tried.

I have two questions:

  1. Is there a good explanation for this seeming connection between the eigenvectors of the truncated harmonic series matrix and Pascal's triangle, assuming my numerical exploration is not a coincidence?

  2. Can we use this to say anything interesting about (the final column of) $A^k$? A closed form that does not require constructing the Pascal triangles perhaps?

orlp
  • 10,508
  • 1
    For curiosity, it is the probability matrix of a markov chain for standing on a stairs $n-1$ steps left to the top and with equal $1/n$ probability to stay on the same stage or go to any other step (but only upwards). – mathreadler Apr 19 '17 at 10:51
  • Maybe there is something with the equidistribution of uniform variables and pascals triangle making successive better approximations to normal (law of large numbers). – mathreadler Apr 19 '17 at 10:54
  • 2
    @mathreadler Yes! The origin is a study of the probability distribution of a $k$-throws dice game where the size of the dice you throw is determined by your previous throw (and initially $n$). – orlp Apr 19 '17 at 10:55
  • This earlier question seems relevant: https://math.stackexchange.com/q/69925/137524. – Semiclassical Apr 19 '17 at 16:00

2 Answers2

2

Since the given matrix is upper triangular, the eigenvalues are trivially $\frac{1}{1},\frac{1}{2},\frac{1}{3},\ldots$ and the shown decomposition is just an instance of the following identity: $$\frac{1}{x(x+1)(x+2)\cdots(x+n)} = \frac{1}{n!}\sum_{k=0}^{n}\frac{(-1)^k}{x+k}\binom{n}{k}$$ that follows from the residue theorem.

Jack D'Aurizio
  • 353,855
  • Could you elaborate a bit on how the decomposition is an instance of the identity? I did manage to find a closed form for the last column of $A^k$ though, if $x$ goes from $1$ to $n$ denoting the row number, then $f_{k, n}(x) = \frac{x}{n} \left | \sum_{i=1}^n \frac{(-1)^i}{i^k}\binom{n}{i}\binom{i}{x} \right |$. – orlp Apr 19 '17 at 12:47
2

Let's indicate your matrix as $$ {\bf A}_{\,h} = \left\| {\;a_{\,n,\,m} \quad \left| {\;0 \le n \le m \le h} \right.\;} \right\| = \left\| {\;{{\left[ {n \le m} \right]} \over {m + 1}}\;} \right\|_{\,h} $$ so that it is a $(h+1) \times (h+1)$ matrix, indexed from $0$, and where the square brackets indicate the Iverson's bracket.

Then let's define $$ \eqalign{ & {\bf E}_{\,h} = \left\| {\;\left[ {n + 1 = m} \right]\;} \right\|_{\,h} \cr & {\bf S}_{\,h} = \left\| {\;\left[ {n \le m} \right]\;} \right\|_{\,h} = {{{\bf I}_{\,h} } \over {{\bf I}_{\,h} - {\bf E}_{\,h} }}\quad \cr & \left( {f(n) \circ {\bf I}_{\,h} } \right) = \left\| {\;f(n)\left[ {n = m} \right]\;} \right\|_{\,h} \cr} $$ so that
${\bf E}_{\,h}$ is the Shifting matrix, with $1$ on the first upper sub-diagonal and null otherwise;
${\bf S}_{\,h}$ is the Summing matrix, upper triangular with all $1$ 's;
$\left( {f(n) \circ {\bf I}_{\,h} } \right)$ is the diagonal matrix, with diagonal elements $f(0),f(1), \cdots, f(h)$.

Then, as you correctly pointed out, we can write: $$ {\bf A}_{\,h} = {\bf S}_{\,h} \left( {{1 \over {n + 1}} \circ {\bf I}_{\,h} } \right) $$ which means $$ {\bf A}_{\,h} ^{\; - \,{\bf 1}} = \left( {\left( {n + 1} \right) \circ {\bf I}_{\,h} } \right)\left( {{\bf I}_{\,h} - {\bf E}_{\,h} } \right) $$

It is not difficult to demonstrate that $$ \eqalign{ & \left( {f(n) \circ {\bf I}_{\,h} } \right)\;{\bf E}_{\,h} = {\bf E}_{\,h} \;\left( {f(n - 1) \circ {\bf I}_{\,h} } \right) = \cr & = \left( {\prod\limits_{0\, \le \,k\, \le \,n - 1} {f(k)} \circ {\bf I}_{\,h} } \right)^{\; - \,{\bf 1}} \;{\bf E}_{\,h} \left( {\prod\limits_{0\, \le \,k\, \le \,n - 1} {f(k)} \circ {\bf I}_{\,h} } \right) \cr} $$ and that, given in general $$ {\bf A}_{\,h} (f) = {\bf S}_{\,h} \left( {f(n) \circ {\bf I}_{\,h} } \right)\quad \left| {\;f(m) \ne f(n)} \right. $$ the relevant matrix of eigenvectors $\mathbf W$ is : $$ {\bf W}_{\,h} (f) = \left\| {\;\left[ {n \le m} \right]{{f(m)^{\,m - n} } \over {\prod\limits_{n\, \le \,k\, \le \,m - 1} {\left( {f(m) - f(k)} \right)} }}\;} \right\|_{\,h} = \left\| {\;\left[ {n \le m} \right]\prod\limits_{n\, \le \,k\, \le \,m - 1} {\left( {{{f(m)} \over {f(m) - f(k)}}} \right)} \;} \right\|_{\,h} $$ while the inverse is: $$ \eqalign{ & {\bf W}_{\,h} ^{\; - \,{\bf 1}} (f)\quad \left| {\;0 \ne f(0)} \right.\quad = \cr & = \left\| {\;\left[ {n \le m} \right]{{f(m)f(n)^{\,m - n - 1} } \over {\prod\limits_{n + 1\, \le \,k\, \le \,m} {\left( {f(n) - f(k)} \right)} }}\;} \right\|_{\,h} = \left\| {\;\left[ {n \le m} \right]{{f(m)} \over {f(n)}}\prod\limits_{n + 1\, \le \,k\, \le \,m} {{{f(n)} \over {\left( {f(n) - f(k)} \right)}}} \;} \right\|_{\,h} \cr} $$

Now, in the present case, we obtain $$ \eqalign{ & {\bf W}_{\,h} = \left\| {\;\left[ {n \le m} \right]\prod\limits_{n\, \le \,k\, \le \,m - 1} {\left( {{{k + 1} \over {k - m}}} \right)} \;} \right\|_{\,h} = \cr & = \left\| {\;\left[ {n \le m} \right]{{m!} \over {n!}}\prod\limits_{1\, \le \,j\, \le \,m - n} {\left( { - {1 \over j}} \right)} \;} \right\|_{\,h} = \left\| {\;\left( { - 1} \right)^{\,m - n} \left( \matrix{ m \cr n \cr} \right)\;} \right\|_{\,h} = \overline {\bf B} _{\,h} ^{\; - \,{\bf 1}} \cr} $$ where $ \overline {\bf B} _{\,h} $ is the transpose of the Lower Triangular Pascal array.

Finally $$ {\bf A}_{\,h} = {\bf S}_{\,h} \left( {{1 \over {n + 1}} \circ {\bf I}_{\,h} } \right) = \overline {\bf B} _{\,h} ^{\; - \,{\bf 1}} \;\left( {{1 \over {n + 1}} \circ {\bf I}_{\,h} } \right)\;\overline {\bf B} _{\,h} $$ which demonstrates your assumption.

Concerning your last question instead, we have of course that $$ {\bf A}_{\,h} ^{\;{\bf q}} = \overline {\bf B} _{\,h} ^{\; - \,{\bf 1}} \;\left( {{1 \over {\left( {n + 1} \right)^{\;q} }} \circ {\bf I}_{\,h} } \right)\;\overline {\bf B} _{\,h} $$ whose single components are: $$ \eqalign{ & a^{\left( q \right)} _{\,n,\,m} = \sum\limits_{0\, \le \,\left( {n\, \le } \right)\,k\,\left( { \le \,m} \right)\, \le \,h} {\left( { - 1} \right)^{\,k - n} \left( \matrix{ k \cr n \cr} \right){1 \over {\left( {k + 1} \right)^{\;q} }}\left( \matrix{ m \cr k \cr} \right)} = \cr & = \sum\limits_{0\, \le \,\left( {n\, \le } \right)\,k\,\left( { \le \,m} \right)\, \le \,h} {\left( { - 1} \right)^{\,k - n} \left( \matrix{ m \cr n \cr} \right)\left( \matrix{ m - n \cr k - n \cr} \right)\left( {k + 1} \right)^{\; - \,q} } = \cr & = \left( \matrix{ m \cr n \cr} \right)\sum\limits_{0\, \le \,\left( {n\, \le } \right)\,k\,\left( { \le \,m} \right)\, \le \,h} {\left( { - 1} \right)^{\,k - n} \left( \matrix{ m - n \cr k - n \cr} \right)\left( {k - n + n + 1} \right)^{\; - \,q} } = \cr & = {{m!} \over {n!}}\sum\limits_{\,0\, \le \,j\, \le \,m - n} {{{\left( { - 1} \right)^{\,j} } \over {j!\left( {m - n - j} \right)!}}\left( {j + n + 1} \right)^{\; - \,q} } \cr} $$ Cannot find at the moment a "more compact" expression.

G Cab
  • 35,272