4
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ 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). $\endgroup$ Apr 19 '17 at 10:51
  • $\begingroup$ Maybe there is something with the equidistribution of uniform variables and pascals triangle making successive better approximations to normal (law of large numbers). $\endgroup$ Apr 19 '17 at 10:54
  • 2
    $\begingroup$ @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$). $\endgroup$
    – orlp
    Apr 19 '17 at 10:55
  • $\begingroup$ This earlier question seems relevant: math.stackexchange.com/q/69925/137524. $\endgroup$ Apr 19 '17 at 16:00
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 |$. $\endgroup$
    – orlp
    Apr 19 '17 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.