Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $s(m,n)$ be the Stirling Numbers of the first kind, $S(m,n)$ be the Stirling Numbers of the second kind.

The matrices $$\mathcal{S}_N := (S(m,n))_{N \geq m,n \geq 0} \text { and } \mathcal{s}_N := (s(m,n))_{N \geq m,n \geq 0}$$ are inverse to each other.

This is a definition in our lecture notes. But why does this apply?

Wikipedia says:

$$\sum_{n=0}^{\max\{j,k\}} (-1)^{n-k} \left[{n\atop j}\right] \left\{{k\atop n}\right\} = \delta_{jk} = \sum_{n=0}^{\max\{j,k\}} (-1)^{n-k} \left\{{n\atop j}\right\} \left[{k\atop n}\right]$$

where $\delta_{jk}$ is the Kronecker delta. But this is neither an explanation (I understand) nor did our lecture cover that "Kronecker Delta".

Could anyone please explain to me?

Thank you in advance!

share|improve this question
5  
The two matrices are the change-of-basis matrices between the basis $\{ 1, x, x^2, ... \}$ of the space of polynomials and the basis $\{ 1, x, x(x-1), x(x-1)(x-2)... \}$ of the space of polynomials. If you know the definitions, it shouldn't be hard to work out the details from here. –  Qiaochu Yuan May 29 '11 at 20:56
    
@qiaochu-yuan This is another defition I found. But I still don't get how this leads me to the fact that the matrices are the inverse of each other. Could you please give me another hint? –  muffel May 29 '11 at 21:15
    
Kronecker delta ... $\delta_{jk}=1$ if $j=k$ and $\delta_{jk} = 0$ otherwise. So this is the entry in row $j$ column $k$ of the identity matrix. –  GEdgar May 29 '11 at 21:56
1  
if one matrix lets you change from basis $B_1$ to $B_2$, and another lets you change from $B_2$ to $B_1$, then their composition in either order is the identity. –  Qiaochu Yuan May 29 '11 at 22:19
add comment

2 Answers 2

up vote 5 down vote accepted

The fact that the two Stirling matrices are inverses is a special case of the fact that certain matrices consisting of elementary and complete symmetric polynomials are inverses.

Define infinite lower triangular matrices $F$ and $G$ consisting of elementary and complete symmetric polynomials, respectively, via
$$(F(z_1, z_2, \ldots,))_{ij} = e_{i-j}(z_1, z_2, \ldots, z_{i-1}),$$ $$(G(z_1, z_2, \ldots,))_{ij} = h_{i-j}(z_1, z_2, \ldots, z_j).$$

For example, if $[F]_n$ and $[G]_n$ denote the $n \times n$ first principal minors of $F$ and $G$, respectively, then $$[F(x,y,z)]_4 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ x & 1 & 0 & 0 \\ xy & x+y & 1 & 0 \\ xyz & xy+xz+yz & x+y+z & 1 \end{bmatrix}$$ and $$ [G(x,y,z)]_4 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ x & 1 & 0 & 0 \\ x^2 & x+y & 1 & 0 \\ x^3 & x^2 + xy + y^2 & x+y+z & 1 \end{bmatrix}.$$

Then $F(1,1,\ldots)$ is the infinite Pascal matrix (consisting of the binomial coefficients), and $F(-1,-2,-3,\ldots)$ is the infinite Stirling matrix of the first kind, so that $$[F(1,1,\ldots)]_4 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 1 & 3 & 3 & 1 \end{bmatrix}, \text{ and } [F(-1,-2,-3,\ldots)]_4 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 2 & -3 & 1 & 0 \\ -6 & 11 & -6 & 1 \end{bmatrix}.$$

Moreover, $G(1,1,\ldots)$ is also the infinite Pascal matrix, and $G(1,2,3,\ldots)$ is the infinite Stirling matrix of the second kind, so that, for example, $$[G(1,1,\ldots)]_4 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 1 & 3 & 3 & 1 \end{bmatrix}, \text{ and } [G(1,2,3,\ldots)]_4 = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 3 & 1 & 0 \\ 1 & 7 & 6 & 1 \end{bmatrix}.$$

In "Symmetric Polynomials, Pascal Matrices, and Stirling Matrices" (Linear Algebra and Its Applications, 428 (4): 1127-1134, 2008) Andy Zimmer and I prove that $$F(z_1,z_2,\ldots) G(-z_1, -z_2, \ldots) = I.$$

Thus the two Stirling matrices are inverse, and (up to sign) the Pascal matrix is its own inverse.

(The fact that the binomial coefficients and the Stirling numbers can be expressed in terms of symmetric polynomials is known; for references, see the paper.)

share|improve this answer
add comment

By definition (at least the one I'm used to), the Stirling numbers of the first kind $S_1(n,k)$ satisfy $$ (x)_n = \sum_{k=0}^n S_1(n,k) x^k, $$ and the Stirling numbers of the second kind $S_2(n,k)$ satisfy $$ x^n = \sum_{k=0}^n S_2(n,k) (x)_k $$ where $(x)_n=x(x-1)\cdots(x-n+1)$ is the falling factorial (with $(x)_0=1$). Combining these yields $$ x^n = \sum_{k=0}^n \sum_{l=0}^k S_2(n,k) S_1(k,l) x^l $$ $$ = \sum_{l=0}^n x^l \left( \sum_{k=l}^n S_2(n,k) S_1(k,l) \right). $$ Comparing powers of $x$, we see that $$ \sum_{k=l}^n S_2(n,k) S_1(k,l) = \left\{ \begin{array}{lr} 1 & \mathrm{ if}\;\; l=n \\ 0 & \mathrm{ if}\;\; l\neq n \end{array} \right.$$ $$ = \delta_{ln}.$$

If we define $S_{\nu}(a,b)=0$ for $a<b$, then this is just the product of the $n^{th}$ row of $S_N$ and the $l^{th}$ column of $s_N$, i.e. the $(n,l)^{th}$ element of the matrix product $S_N s_N$ is $\delta_{nl}$. Thus their product is the identity matrix, and hence they're matrix inverses of eachother.

[Edit] Another way (less computation, slightly more hand-wavy) to see this is that $S_N$ is the change of basis matrix (for the space of polynomials) from $\{1,x,x^2,\dots\}$ to $\{(x)_0, (x)_1, \dots\}$, and $s_N$ is the change of basis matrix going the other way. Hence the linear transformation $S_Ns_N$ takes the coefficients in terms of $\{x^i\}$ to coefficients in terms of $\{(x)_i\}$ and then back to $\{x^i\}$, i.e. it's the identity.

share|improve this answer
    
great, thank you! –  muffel May 30 '11 at 7:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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