% MuirRecurrents.tex
\documentclass[a4paper,12pt]{article}
\usepackage{amsmath,amsfonts,amssymb,amsthm}

\long\def\bee#1\ee{\begin{equation}#1\end{equation}}
\def\be{\begin{equation}}


\def\s{\scriptstyle }
\def\a{\alpha}
\def\b{\beta}
\def\l{\lambda}
\def\e{\epsilon}
\def\L{\Lambda}
\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\A{{\mathbb A}}
\def\B{{\mathbb B}}
\def\C{{\mathbb C}}
\def\X{{\mathbb X}}
\def\Y{{\mathbb Y}}
\def\AB{ {\mathbb A}\moins {\mathbb B}}
\def\ss{\sigma}
\def\Sym{{\mathfrak Sym}}
\def\cO{{\mathcal O}}
\def\Sp{{\mathcal Sp}}

\def\bu{\scriptstyle \bullet}
\def\moins{\raise 1pt\hbox{$\s -$}}
\def\plus{\raise 1pt \hbox{ $\s +$}}

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\def\proof{\noindent{\it Proof.}\ }

\begin{document}
\title{Muir and the Theory of Recurrents}
\author{
Alain Lascoux\\
{\small Institut Gaspard Monge, CNRS, Universit\'e de Marne-la-Vall\'ee}\\
{\small 77454 Marne-la-Vall\'ee Cedex, France}\\
{\small e-mail: Alain.Lascoux @ univ-mlv.fr}\\
}
\date{}
\maketitle

\begin{abstract}
\end{abstract}

\section{Introduction}
The five volumes of Muir's ``History ... of determinants''
are without equivalent in the mathematical literature. He succeeded
in giving a fairly complete and comprehensive survey of all
the literature pertaining ot determinants, from the very first
beginnings till his time. Only the last period (1900-1920)  
is not exhaustively covered, with developments in geometry and group
representations hardly evoked. 

Muir thought of summarizing the main properties
of determinants in a single volume
``A Treatise on the Theory of Determinants'', which was revised and
enlarged by W. Metzler, a copy of which I owe to the generosity of 
G.C. Rota. Thus, we can take the ``Treatise'' as a testimony of 
what Muir considered to be the main properties of determinants, 
as extracted from his five volumes, or his personal 300 articles
on the subject.

As in many fields in mathematics, at a certain point of development,
more and more specialized articles about seemingly more and special
determinants, as well as generalizations without applications,
were published, and this certainly discouraged mathematicians
in other fields from looking at this literature. 
Another factor is that linear algebra, and commutative diagrams,
can dispense of some of the properties of determinants in a more
powerful way than manipulating algebraic identities only.

Of course the theory of determinants receives a new impetus
from time to time, from combinatorics, group representations
and statistical models in theoretical physics 
recently.   

I shall examine in this text the contribution of Muir to
the theory of recurrents.
As a matter of fact, Muir does not define the term \emph{recurrent}, 
leaving it imprecise enough to cover all type of determinants which
arise in relation with linear recurrences, Taylor expansion
of rational functions and so like. Thus the only working definition
that I can take is that a recurrent is recurrent because 
it belongs to a chapter with this headline in one of the five
volumes of the ``History'', or in the volume of the  ``Theory''.


Recurrents  can be treated using the theory of symmetric functions.
Indeed many determinants occur in this last theory,
and conversely, using the combinatorics of symmetric functions,
and more generally, of the symmetric group, provides
powerful methods to manipulate determinants. The main 
symmetric functions, the \emph{Schur functions},
can be written in at least half a dozen ways as determinants,
but most of their properties are proven without having
recourse to the theory of determinants. In the other direction, 
relations as simple as Pl\"ucker relations give quadratic
identities on Schur functions that one would have much
difficulties to obtain from the known rules for
multiplying Schur functions. 


\section{Symmetric functions and Determinants}

Given two finite sets $\A,\B$ of variables (we say \emph{alphabets}),
one defines the complete functions 
$S^i(\AB)$ of the the formal difference $\AB$ by the generating
function ($z$ is an extra variable)
\begin{equation}
 \ss_z(\A - \B):=  {\prod_{b\in \B} (1-zb) \over \prod_{a\in \A}  (1-za)}
\end{equation}

Similarly, the \emph{power sums}  $\Psi^i(\AB)$ are defined by
\begin{equation}
\log\left(\ss_z(\A)\right) = \sum_1^\infty \, \Psi^i(\AB) \, z^i/i    \, .
\end{equation}

The relations between the functions $\Psi^i(\AB)$, $S^i(\AB)$,
$S^i(\A)$, $S^i(\moins \B)$ can be expressed through different
determinants (not writing the argument
when it is the same for all the symmetric functions appearing 
in the equation)~:

\begin{equation}    \label{e2h}
 (-1)^n S^n(\moins \A)  =
 \begin{vmatrix}
     S^1(\A) & S^2(\A) &\cdots & S^n(\A) \\
     S^0(\A) & S^1(\A) &  \cdots & S^{n-1}(\A) \\
    \vdots  &        & \vdots  \\
     S^{2-n}(\A) & S^{1-n}(\A)& \cdots & S^1(\A) 
\end{vmatrix} \,
\end{equation}
\begin{equation}    \label{p2h}
\Psi^n=  \begin{vmatrix} n\, S^n&S^1&\ldots&S^n\cr
                      (n\moins1)S^{n-1}&S^0&\ldots&S^{n-1}\cr
                      \vdots&\vdots&\ddots&\vdots\cr
                      0\, S_0&.&\ldots&S^0
\end{vmatrix}
\end{equation}
\begin{equation}    \label{h2p}
 n!\,S^n=  \begin{vmatrix}
 \Psi^1&-1&0&\ldots&0\cr \Psi^2&\Psi^1&-2&\ldots&0\cr
                    \vdots&\vdots&\vdots&\ddots&\vdots\cr
                    \Psi^{n-1}&\Psi _{n-2}&\Psi^{n-3}&\ldots&1\moins n\cr
                    \Psi^n&\Psi^{n-1}&\Psi^{n-2}&\ldots&\Psi^1 
\end{vmatrix} \,
\end{equation}
\begin{equation}     \label{S(A-B)}
S^n(\AB) = \begin{vmatrix}
S^n(\A)     & S^1(\B) & \cdots & S^n(\B) \\
S^{n-1}(\A) & S^0(\B) & \cdots & S^{n-1}(\B) \\
\vdots      & \vdots  &        & \vdots  \\
S^0(\A) & S^{1-n}(\B) & \cdots & S^0(\B)  
\end{vmatrix}
\end{equation}



One can use these determinants without reference to the theory of
symmetric functions. Indeed, one can start with any formal series
$f= 1+\sum_1^\infty z^n S^n$, instead
of $\ss_z(\A)$.   The relations between the coefficients of
$f$, $f^k$, $k\in\C$, and $\log(f)$ remain the same as when taking  
$\ss_z(\A)$ with  $\A$ of infinite cardinality.  
However, factorizing formally $f$, i.e. deciding to write
$f=\ss_z(\A)$ usually simplifies the algebraic manipulation
of formal series, as it does in the case of polynomials, 
when considering their roots instead of only their coefficients. 


For example, Muir gives several determinantal expressions of
Bernoulli numbers $B_n$. Their exponential generating function is
$$ f= \sum_0^\infty z^n B_n/n! = z (1-\exp(\moins z))^{-1}  \ .$$

Writing $f=\ss_z(\A)$ means that we introduce a ``Bernoulli alphabet''
$\A$ such that 
$ S^n(\A)= B_n/n!$.

But this alphabet can be as well defined by either system of equations
\begin{eqnarray}   
  S^n(-\A)  &=&  1/(n+1) ! \ n\geq 0  \, ,  \\
  \Psi^n(\A) &=& -S^n(\A)  \ n\geq 2  \, , \\
  S^n( (n\plus 1)\A) &=& 1  \ n\geq 2,\,  S^1(\A)=\moins 1/2 \ ,
\end{eqnarray}
considering $1/f$ or $\log(f)$ instead of $f$, for the first two.
The last system
of equations is given by the Lagrange inversion of
formal series; though a little unusual, it is the precise characterization
of Bernoulli numbers which is needed by Hirzebruch 
\cite[Lemma 1.7.1]{Hirzebruch}
to define Todd classes. In other terms, the last equations
 asssert that the coefficient 
of $z^n$ in $\bigl(z (1-\exp(\moins z))^{-1}   \bigr)^{n+1}$ is equal to
$1$.    

Replacing in the determinants (\ref{e2h}, \ref{p2h}, \ref{h2p},
\ref{S(A-B)})
 the symmetric functions of $\A$
by their explicit values give without computations
relations involving Bernoulli numbers, 
inverses of factorials, or binomial coefficients
from which one can deduce different special recurrents 
figuring  in different places of Muir's  History. 

\section{A specific example involving Catalan numbers}

In \cite{Muir1918}, Theory p.731-732, 
Muir gives two determinants of binomial coefficients 
which factorize into products of consecutive odd integers.

Specifically, for $n\in \N$, let 
$$ R_n =
 \begin{vmatrix}  
 \binom{1}{0}   &\moins 2 &0 &0 &\cdots \\[3pt]
 \binom{3}{1}  & \binom{1}{0}  &\moins 4 &0 &\cdots  \\[3pt]
   \binom{5}{2} & \binom{3}{1}  & \binom{1}{0}  &\moins 6 &  \\[3pt]
   \vdots       &\vdots  && & \ddots  \\[3pt]
   \binom{2n-1}{n-1} & \binom{2n-3}{n-2} & \cdots  & \cdots & \binom{1}{0}
  \end{vmatrix}  \ ,
$$
the overdiagonal being $\moins 2,\, \moins 4,\, \ldots,
-(2n\moins 2)$.

Muir shows by recursion on $n$ that 
$$ R_n = (2n\plus 3) (2n\plus5)\cdots (4n\moins 3)(4n\moins1) \ . $$

How to interpret and generalize such a result ?

First, the determinant is of the type (\ref{h2p}), after dividing 
each entry by $2$. More generally, for any $k\in\C$, let us 
define $M_n$ to be the image of the determinant (\ref{h2p}) 
under the  specialization $\Psi^i(\A_k)= k\binom{2i-1}{i-1} $
(we have indexed the alphabet by $k$ to show its dependency upon $k$).

But in the case $k=1$, $C(z):=\sigma_z(\A_1)$ is the generating function
of Catalan numbers :
$$  \Psi^i(\A_1)=  \binom{2i-1}{i-1}  \ \Rightarrow 
 S^i(\A_1) = \binom{2i}{i-1}/(i\plus 1) \ .   $$

Therefore, 
$$ \sigma_z(\A_k) = \left(\sigma_z(\A_1) \right)^k  =  C(z)^k =
  \left(\frac{1-\sqrt{1-4z}}{2z}  \right)^k   \, . $$

Using the functional equation $zC(z)^2-C(z)+1=0$, or rather,
$$  zC(z)^{k+2}-C(z)^{k+1} + C(z)^k=0 \ ,  $$
one gets the relations
\begin{equation}
 S^{n-1}(A_{k+2}) - S^{n}(A_{k+1}) +S^{n}(A_{k}) = 0  \ ,
\end{equation}
and this allows to determine the complete functions 
of $A_{k}$, when $k$ is a positive ineger,
 supposing known those of $\A_0$ and $\A_1$. 
These expressions remain valid for any $k$, because they 
are polynomials in $k$, and one obtain the identity 
\begin{equation}
  S^n(\A_k)  = \frac{k}{n+k}\, \binom{k+2n-1}{n}   \ .
\end{equation}

In conclusion, one has that the determinant
$$   
\begin{vmatrix}
 k\binom{1}{0}   &\moins 1 &0 &0 &\cdots \\[3pt]
 k\binom{3}{1}  & k\binom{1}{0}  &\moins 2 &0 &\cdots  \\[3pt]
 k  \binom{5}{2} & k\binom{3}{1}  & k\binom{1}{0}  &\moins 3 &  \\[3pt]
   \vdots       &\vdots  && & \ddots  \\[3pt]
 k\binom{2n-1}{n-1} & k\binom{2n-3}{n-2} & \cdots  & \cdots & k\binom{1}{0}
  \end{vmatrix}  \
$$
is equal to 
$$ \frac{k\, (k\plus 2n\moins 1)!}{(k\plus n)!} ,   $$
the cases considered by Muir being  $k=\pm 1/2$.  


One can modify the last row of the determinant, by taking an extra 
parameter $r$, and replacing in this row
$k\binom{2n+1-2j}{n-j}$   by 
$$ \binom{2n+1-2j+r}{n-j}  \ ,\ j=1,\ldots,n \, .$$

An easy computation shows that the determinant still
factorizes, and is equal to 
\begin{equation}
 (n+1+k+r) (n+2+k+r)\cdots (2n-1+k+r) \ .
\end{equation}

The transformation has the same effect as a shifting $k$ to $k+r$. 


\begin{thebibliography}{1}

\bibitem{Hirzebruch}  F. Hirzebruch,
\emph{Toplogical Methods in Algebraic Geometry},
Third ed., Springer (1966).

\bibitem{Muir1918} T. Muir,
 \emph{Note on recurrents resolvable into a sequence of
odd integers}, Trans. Royal Soc. of South Africa  {\bf 8} (1919) 27--32.

\bibitem{MM} T. Muir, W. Metzler.
\emph{A Treatise on the Theory of Determinants}, 
Longmans, Green and Co (1933).


\end{thebibliography}

\end{document}


