text:
# 1 Introduction and summary

## 1 Introduction and summary

For $`k2`$, denote the set of probability distributions on $`\{1,\mathrm{},k\}`$ by $`𝒫_k`$. Let $`(\xi _m,m1)`$ be a sequence of independent random variables with common distribution $`p𝒫_k`$ and, for $`1ik`$, $`n0`$, set

$$X_i(n)=|\{1mn:\xi _m=i\}|.$$
(1)
If $`p_1<\mathrm{}<p_k`$, there is a positive probability that the random walk $`X=(X_1,\mathrm{},X_k)`$ never exits the Weyl chamber

$$W=\{x^k:x_1\mathrm{}x_k\};$$
(2)
this is easily verified using, for example, the concentration inequality

$$P(|X(n)np|>\epsilon )Ke^{c(\epsilon )n},$$

where $`c(\epsilon )`$ and $`K`$ are finite positive constants.

In , a certain path-transformation $`G^{(k)}`$ was introduced with the property that:

###### Theorem 1.1

The law of the transformed walk $`G^{(k)}(X)`$ is the same, assuming $`p_1<\mathrm{}<p_k`$, as that of the original walk $`X`$ conditioned never to exit $`W`$.

We will recall the definition of $`G^{(k)}`$ in Section 2 below.

This was motivated by a desire to find a multi-dimensional generalisation of Pitman’s representation for the three-dimensional Bessel process , and to understand some striking connections which were recently discovered by Baik, Deift and Johansson , Baryshnikov  and Gravner, Tracy and Widom , between oriented percolation and random matrices. For more background on this, see .

The proof of Theorem 1.1 given in  uses certain symmetry and reversibility properties of M/M/1 queues in series; consequently, the transformation $`G^{(k)}`$ has a ‘queueing-theoretic’ interpretation.

In this paper we will show that the path-transformation $`G^{(k)}`$ is closely related to the Robinson-Schensted correspondence. More precisely, if $`\lambda (n)=(\lambda _1(n)\mathrm{}\lambda _k(n))`$ denotes the shape of the Young tableaux obtained, when one applies the Robinson-Schensted algorithm, with column-insertion, to the random word $`\xi _1\mathrm{}\xi _n`$, then (for any realisation of $`X`$)

$$(G^{(k)}(X))(n)=(\lambda _k(n),\mathrm{},\lambda _1(n)).$$

Immediately, this yields a new representation and formula for the Robinson-Schensted algorithm, and this formula has a queueing interpretation. We will use this representation to recover known, and perhaps not-so-well-known, properties of the Robinson-Schensted algorithm.

Given this connection, Theorem 1.1 can now be interpreted as a statement about the evolution of the shape $`\lambda (n)`$ of a certain randomly growing Young tableau. We give a direct proof of this result using properties of the Robinson-Schensted correspondence. This also yields more information about the joint law of $`X`$ and $`G^{(k)}(X)`$, and dispenses with the condition $`p_1<\mathrm{}<p_k`$.

As in , the corresponding results for the Brownian motion model can be recovered by Donsker’s theorem. The path-transformation $`G^{(k)}`$ extends naturally to a continuous setting and, given the connection with the Robinson-Schensted algorithm, the continuous version can now be regarded as a natural extension of the Robinson-Schensted algorithm to a continuous setting. As discussed in , the results for Brownian motion have an interpretation in random matrix theory. In particular, Theorem 1.1 yields a representation for the eigenvalue process associated with Hermitian Brownian motion as a certain path-transformation (the continuous analogue of $`G^{(k)}`$) applied to a standard Brownian motion. The new results presented in this paper also yield new results in this context. This random matrix connection comes from the well-known fact that the eigenvalue process associated with Hermitian Brownian motion can be interpreted as Brownian motion conditioned never to exit the Weyl chamber $`W`$. We remark that a similar representation for the eigenvalues of Hermitian Brownian motion was independently obtained by Bougerol and Jeulin , in a more general context, by completely different methods.

The outline of the paper is as follows. In the next section we recall the definition of $`G^{(k)}`$ and record some of its properties. In section 3, we make the connection with the Robinson-Schensted algorithm, and briefly consider some immediate implications of this connection. A worked example is presented in section 4. In section 5, we record some properties of the conditioned walk of Theorem 1.1 and extend its definition beyond the case $`p_1<\mathrm{}<p_k`$. In section 6, we prove a generalisation of Theorem 1.1, in the context of Young tableaux, using properties of the RS correspondence. In section 7, we define a continuous version of the path-transformation and present the ‘Poissonized’ analogues of the results of the previous section. In section 8, we present the corresponding results for the Brownian model, and briefly discuss the connection with random matrices. An application in queueing theory is presented in section 9, and we conclude the paper with some remarks in section 10.

Some notation: Let $`b=\{e_1,\mathrm{},e_k\}`$ denote the standard basis elements in $`^k`$. For $`x,y_+^k`$ we will write $`x^y=x_1^{y_1}\mathrm{}x_k^{y_k}`$, $`xy=(x_1y_1,\mathrm{},x_ky_k)`$, $`|x|=_ix_i`$ and define $`x^{}_+^k`$ by $`x_i^{}=x_{ki+1}`$. Denote the origin in $`^k`$ by $`o`$.

Acknowledgements: Thanks to Francois Baccelli, Phillipe Biane, Phillipe Bougerol and Marc Yor for many helpful and illuminating discussions on these topics. This research was partly carried out during a visit, funded by the CNRS, to the Laboratoire de Probabilités, Paris 6, and partly at the ENS, thanks to financial support of INRIA.

## 2 The path-transformation

The support of the random walk $`X`$, which we denote by $`\mathrm{\Pi }_k`$, consists of paths $`x:_+_+^k`$ with $`x(0)=0`$ and, for each $`n>0`$, $`x(n)x(n1)b`$. Let $`\mathrm{\Pi }_k^W`$ denote the subset of those paths taking values in $`W`$. It is convenient to introduce another set $`\mathrm{\Lambda }_k`$ of paths $`x:_+_+^k`$ with $`x(0)=0`$ and $`x(n)x(n1)\{0,e_1,\mathrm{},e_k\}`$, for each $`n>0`$.

For $`x,y\mathrm{\Lambda }_1`$, define $`xy\mathrm{\Lambda }_1`$ and $`xy\mathrm{\Lambda }_1`$ by

$$(xy)(n)=\underset{0mn}{\mathrm{min}}[x(m)+y(n)y(m)],$$
(3)
and

$$(xy)(n)=\underset{0mn}{\mathrm{max}}[x(m)+y(n)y(m)].$$
(4)
The operations $``$ and $``$ are not associative in general. Unless otherwise deleniated by parentheses, the default order of operations is from left to right; for example, when we write $`xyz`$, we mean $`(xy)z`$.

The mappings $`G^{(k)}:\mathrm{\Lambda }_k\mathrm{\Lambda }_k`$ are defined as follows. Set

$$G^{(2)}(x,y)=(xy,yx)$$
(5)
and, for $`k>2`$,

$`G^{(k)}(x_1,`$ $`\mathrm{},x_k)=(x_1x_2\mathrm{}x_k,`$
$`G^{(k1)}(x_2x_1,x_3(x_1x_2),\mathrm{},x_k(x_1\mathrm{}x_{k1}))).`$ (6)
Note that $`G^{(k)}:\mathrm{\Pi }_k\mathrm{\Pi }_k^W`$.

We will now give an alternative definition of $`G^{(k)}`$ which will be useful for making the connection with the Robinson-Schensted correspondence.

Occasionally, we will suppress the dependence of functions on $`x`$, when the context is clear: for example, we may write $`G^{(k)}`$ instead of $`G^{(k)}(x)`$, and so on.

For $`k2`$, define maps $`D^{(k)}:\mathrm{\Lambda }_k\mathrm{\Lambda }_k`$ and $`T^{(k)}:\mathrm{\Lambda }_k\mathrm{\Lambda }_{k1}`$, by

$$D^{(k)}(x)=(x_1,x_1x_2,\mathrm{},x_1\mathrm{}x_k)$$
(7)
and

$$T^{(k)}(x)=(x_2x_1,x_3(x_1x_2),\mathrm{},x_k(x_1\mathrm{}x_{k1})).$$
(8)
For notational convenience, let $`D^{(1)}`$ be the identity transformation.

Note that the above definition is recursive: for $`i2`$,

$$D_i^{(k)}=D_{i1}^{(k)}x_i,$$
(9)
and

$$T_{i1}^{(k)}=x_iD_{i1}^{(k)}.$$
(10)
Alternatively, we can write

$$(D_i^{(k)},T_{i1}^{(k)})=G^{(2)}(D_{i1}^{(k)},x_i).$$
(11)
For each $`x\mathrm{\Lambda }_k`$, consider the triangular array of sequences $`d^{(i)}\mathrm{\Lambda }_{ki+1}`$, $`1ik`$, defined as follows. Set

$$d^{(1)}=D^{(k)}(x),t^{(1)}=T^{(k)}(x),$$

$$d^{(2)}=D^{(k1)}(t^{(1)}),t^{(2)}=T^{(k1)}(t^{(1)}),$$

and so on; for $`ik`$,

$$d^{(i)}=D^{(ki+1)}(t^{(i1)}),$$

and for $`ik1`$,

$$t^{(i)}=T^{(ki+1)}(t^{(i1)}).$$

Recalling the definition of $`G^{(k)}`$ given earlier, we see that

$$G^{(k)}=(d_k^{(1)},\mathrm{},d_1^{(k)}).$$
(12)
Note also that, for each $`ik`$,

$$G^{(i)}(x_1,\mathrm{},x_i)=(d_i^{(1)},\mathrm{},d_1^{(i)}).$$
(13)
We will conclude this section by recording some useful properties and interpretations of the operations $``$ and $``$, and of the path-transformation $`G^{(k)}`$, for later reference. We defer the proofs: these will be given in the appendix.

The following notation for increments of paths will be useful: for $`x\mathrm{\Lambda }_k`$ and $`ln`$, set $`x(n,l)=x(l)x(n)`$.

The operations $``$ and $``$ have a queueing-theoretic interpretation, which we will make strong use of when we make the connection with the Robinson-Schensted correspondence in the next section. For more general discussions on ‘min-plus algebra’ and queueing networks, see .

Suppose $`(x,y)\mathrm{\Pi }_2`$, and consider a simple queue which evolves as follows. At each time $`n`$, either $`x(n)x(n1)=1`$ and $`y(n)y(n1)=0`$, in which case a new customer arrives at the queue, or $`x(n)x(n1)=0`$ and $`y(n)y(n1)=1`$, in which case, if the queue is not empty, a customer departs (otherwise nothing happens). The number of customers remaining in the queue at time $`n`$, which we denote by $`q(n)`$, satisfies the Lindley recursion

$$q(n)=\mathrm{max}\{q(n1)+ϵ(n),0\},$$
(14)
where $`ϵ(n)=x(n)x(n1)y(n)+y(n1)`$. Iterating (14), we obtain

$$q(n)=\underset{0mn}{\mathrm{max}}[x(m,n)y(m,n)].$$
(15)
Thus, the number of customers $`d(n)`$ to depart up to and including time $`n`$ is given by

$$d(n)=x(n)q(n)=(xy)(n).$$
(16)
We also have

$$t(n):=x(n)+u(n)=(yx)(n),$$
(17)
where

$$u(n)=y(n)d(n)$$

is the number of times $`mn`$ that $`y(m)y(m1)=1`$ and $`q(m1)=0`$; in the language of queueing theory, $`u(n)`$ is the number of ‘unused services’ up to and including time $`n`$. (For this queue we refer to the points of increase of $`y`$ as ‘services’.)

###### Lemma 2.1

For $`(x,y)\mathrm{\Lambda }_2`$,

$$xy+yx=x+y,$$
(18)
and

$`x(n)(xy)(n)`$ $`=`$ $`\underset{0mn}{\mathrm{max}}[x(m,n)y(m,n)]`$
$`=`$ $`\underset{ln}{\mathrm{max}}[(xy)(n,l)(yx)(n,l)].`$
In particular, writing $`G^{(2)}G^{(2)}(x,y)`$, we have:

$$(x(n),y(n))=G^{(2)}(n)+F^{(2)}\left(G^{(2)}(n,l),ln\right),$$
(19)
where $`F^{(2)}:𝒟^2`$ is defined, on

$$𝒟=\{z(^2)^_+:M(z)=\underset{n0}{\mathrm{max}}[z_1(n)z_2(n)]<\mathrm{}\},$$

by $`F^{(2)}(z)=(M(z),M(z))`$.

In the queueing context described above, the above lemma states that $`x+y=d+t`$ and

$$q(n)=\underset{mn}{\mathrm{max}}[d(n,m)t(n,m)].$$
(20)
The first identity is readily verified. The formula for $`q(n)`$ in terms of the future increments of $`d`$ and $`t`$ follows from the time-reversal symmetry in the dynamics of the system: this formula is the dual of (15). When time is reversed, the roles played by $`(x,y)`$ and $`(d,t)`$ are interchanged. This symmetry is at the heart of the proof of Theorem 1.1 given in , where it is considered in an equilibrium context.

Note that, if we set $`z=yx`$ and $`s(n)=\mathrm{max}_{0mn}z(m)`$, then

$$yxxy=2sz$$

and (20) is equivalent to the well-known identity

$$s(n)=\underset{ln}{\mathrm{min}}[2s(l)z(l)].$$

This is familiar in the context of Pitman’s representation for the three-dimensional Bessel process. Observe that the statement of Theorem 1.1 in the case $`k=2`$ is equivalent to the following discrete version of Pitman’s theorem: if $`\{Z(n),n0\}`$ is a simple random walk on $``$ with positive drift, started at $`0`$, and we set $`S(n)=\mathrm{max}_{0mn}Z(n)`$, then $`2SZ`$ has the same law as that of $`Z`$ conditioned to stay non-negative. The usual statement of Pitman’s theorem can be recovered from Theorem 8.1 below.

Lemma 2.1 has the following generalisation:

###### Lemma 2.2

For $`x\mathrm{\Lambda }_k`$, writing $`G^{(k)}G^{(k)}(x)`$,

$$|G^{(k)}|=|x|,$$
(21)
and

$$x(n)=G^{(k)}(n)+F^{(k)}\left(G^{(k)}(n,l),ln\right),$$
(22)
where the function $`F^{(k)}`$ will be defined in the proof.

As we remarked earlier, the operations $``$ and $``$ are not associative. The following identities are useful for manipulating complex combinations of these operations.

###### Lemma 2.3

For $`(a,b,c)\mathrm{\Lambda }_3`$,

$$a(cb)(bc)=abc,$$
(23)
and

$$a(cb)(bc)=abc.$$
(24)
For example, (23) immediately yields:

###### Lemma 2.4

For $`x\mathrm{\Lambda }_k`$, $`G_k^{(k)}(x)=x_k\mathrm{}x_1`$.

## 3 Connection with the Robinson-Schensted algorithm

We refer the reader to the books of Fulton  and Stanley  for detailed discussions on the Robinson-Schensted algorithm and its properties. The standard Robinson-Schensted algorithm takes a word $`w=a_1\mathrm{}a_n\{1,2,\mathrm{},k\}^n`$ and proceeds, by ‘row-inserting’ the numbers $`a_1`$, then $`a_2`$, and so on, to construct a semistandard tableau $`P(w)`$ associated with $`w`$, of size $`n`$ with entries from the set $`\{1,2,\mathrm{},k\}`$. If one also maintains a ‘recording tableau’ $`Q(w)`$, which is standard tableau of size $`n`$, the mapping from words $`\{1,2,\mathrm{},k\}^n`$ to pairs of semistandard and standard tableaux of size $`n`$, the semistandard tableau having entries from $`\{1,2,\mathrm{},k\}`$ and both having the same shape, is a bijection: this is the Robinson-Schensted correspondence. One can also do all of the above using ‘column-insertion’ instead of row-insertion to construct the semistandard tableau, but still maintaining a recording tableau, and the resulting map is also a bijection. Column and row insertion are not the same thing, but they are related in the following way: the semistandard tableau obtained by applying the Robinson-Schensted algorithm, with column-insertion, to the word $`a_1\mathrm{}a_n`$ is the same as the one obtained by applying the Robinson-Schensted algorithm, with row-insertion, to the reversed word $`a_n\mathrm{}a_1`$. The standard tableaux obtained in each case are also related, but we do not need this and refer the reader to  for details.

Fix $`x\mathrm{\Pi }_k`$, the let $`d^{(i)}\mathrm{\Lambda }_{ki+1}`$, $`1ik`$, be the corresponding triangular array of sequences defined in the previous section.

For each $`n`$, construct a semistandard Young tableau as follows. In the first row, put

$$d_1^{(1)}(n)\text{ 1’s, }d_1^{(2)}(n)d_1^{(1)}(n)\text{ 2’s, }\mathrm{}d_1^{(k)}(n)d_1^{(k1)}(n)\text{ }k\text{’s; }$$

in the second row, put

$$d_2^{(1)}(n)\text{ 2’s, }d_2^{(2)}(n)d_2^{(1)}(n)\text{ 3’s, }\mathrm{}d_2^{(k1)}(n)d_2^{(k2)}(n)\text{ }k\text{’s; }$$

and so on. In the final row, there are just $`d_k^{(1)}(n)`$ $`k`$’s. Denote this tableau by $`\tau (n)`$. For example, if $`k=3`$ and

$$\begin{array}{ccc}d_1^{(1)}(7)& d_2^{(1)}(7)& d_3^{(1)}(7)\\ & d_1^{(2)}(7)& d_2^{(2)}(7)\\ & & d_1^{(3)}(7)\end{array}=\begin{array}{ccc}2& 2& 1\\ & 3& 2\\ & & 4\end{array}$$
(25)
then the corresponding semistandard tableau $`\tau (7)`$ is

| 1 | 1 | 2 | 3 |
| --- | --- | --- | --- |
| 2 | 2 |
| 3 |

(26)
Let $`a_m`$ be the sequence defined by $`a_m=i`$ whenever

$$x(m)x(m1)=e_i.$$

###### Theorem 3.1

The semistandard tableau $`\tau (n)`$ is precisely the one which is obtained when one applies the Robinson-Schensted algorithm, with column insertion, to the word $`a_1\mathrm{}a_n`$. In particular, if $`l(n)`$ denotes the shape of $`\tau (n)`$, then $`l(n)^{}=(G^{(k)}(x))(n)`$.

Proof: It will suffice to describe how the mapping $`G^{(k)}`$ acts on a typical element of $`\mathrm{\Pi }_k`$, from an algorithmic point of view.

For each $`k2`$, the maps $`D^{(k)}:\mathrm{\Lambda }_k\mathrm{\Lambda }_k`$ and $`T^{(k)}:\mathrm{\Lambda }_k\mathrm{\Lambda }_{k1}`$ can be defined as follows. Fix $`x\mathrm{\Pi }_k`$ and set $`d=D^{(k)}(x)`$, $`t=T^{(k)}(x)`$. Set $`d(0)=t(0)=0`$, and define the sequences $`d(n)`$ and $`t(n)`$ inductively on $`n`$. Suppose $`x(n)x(n1)=e_i`$; that is, $`a_n=i`$. We need to treat the cases $`i=1`$ and $`i=k`$ separately.

Suppose $`i=1`$. Then we set $`d(n)=d(n1)+e_1`$ and $`t(n)=t(n1)+e_1`$.

If $`i=k`$, and $`d_k(n1)<d_{k1}(n1)`$, we set $`d(n)=d(n1)+e_k`$ and $`t(n)=t(n1)`$.

If $`i=k`$, and $`d_k(n1)=d_{k1}(n1)`$, we set $`d(n)=d(n1)`$ and $`t(n)=t(n1)+e_{k1}`$.

Now suppose $`1<i<k`$. If $`d_i(n1)<d_{i1}(n1)`$, set $`d(n)=d(n1)+e_i`$ and $`t(n)=t(n1)+e_i`$; if $`d_i(n1)=d_{i1}(n1)`$, set $`d(n)=d(n1)`$ and $`t(n)=t(n1)+e_{i1}`$. Recall that $`D^{(1)}`$ is the identity transformation.

In queueing language, we have just constucted a series of $`k`$ queues in tandem. Initially there are infinitely many customers in the first queue and the other queues are all empty. At each time $`n`$, if $`x_i(n+1)x_i(n)=1`$ (or, equivalently, $`a_n=i`$) there is a ‘service event’ at the $`i^{th}`$ queue; if this queue is not empty a customer departs from it and, if $`i<k`$, joins the $`(i+1)^{th}`$ queue. The number of departures from the $`i^{th}`$ queue up to and including time $`n`$ is given by $`d_i(n)`$ and $`t_i(n)=d_i(n)+u_i(n)`$, where $`u_i(n)`$ is the number of ‘unused services’ at the $`(i+1)^{th}`$ queue up to and including time $`n`$. Recalling the queueing-theoretic interpretations of $``$ and $``$, we see that $`d_i=x_1\mathrm{}x_i`$ and $`t_i=x_id_{i1}`$.

Now fix $`x\mathrm{\Pi }_k`$, and recall the definition of the triangular array of sequences $`d^{(i)}\mathrm{\Lambda }_{ki+1}`$, $`1ik`$. Set

$$d^{(1)}=D^{(k)}(x),t^{(1)}=T^{(k)}(x),$$

$$d^{(2)}=D^{(k1)}(t^{(1)}),t^{(2)}=T^{(k1)}(t^{(1)}),$$

and so on; for $`ik`$,

$$d^{(i)}=D^{(ki+1)}(t^{(i1)}),$$

and for $`ik1`$,

$$t^{(i)}=T^{(ki+1)}(t^{(i1)}).$$

Here we have constructed a ‘series of queues in series’, the entire system ‘driven’ by $`x`$. This is represented in Figure 1 for the case $`k=3`$.

The first series of queues is just the one described above: there are $`k`$ queues in series, and initially queues $`2`$ thru $`k`$ are empty and the first queue has infinitely many customers; whenever $`x_i`$ increases by one there is a service at the $`i^{th}`$ queue and one customer is permitted to depart (and proceed to the next queue if $`i<k`$). The number of departures from the $`i^{th}`$ queue up to time $`n`$ is given by $`d_i^{(1)}(n)`$.

The second series of queues has $`t^{(1)}`$ ‘moving’ the customers in place of $`x`$. This time there are $`k1`$ queues. Initially, queues $`2`$ thru $`k1`$ are empty and the first queue has infinitely many customers. There is a service event at the $`i^{th}`$ queue whenever $`t_i^{(1)}`$ increases by one—that is, whenever, in the first series, there is a departure from the $`i^{th}`$ queue or an unused service at the $`(i+1)^{th}`$ queue (these events will never occur simultaneously).

The second series generates a new sequence of ‘t’s’, which we denote by $`t^{(2)}`$, and this is used to drive the third series, which consists of $`k2`$ queues, and so on.

It is useful to define

$$q_i^{(j)}=d_i^{(j)}d_{i+1}^{(j)};$$
(27)
$`q_i^{(j)}(n)`$ is just the number of customers in the $`(i+1)^{th}`$ queue of the $`j^{th}`$ series at time $`n`$. For example, in the network shown in Figure 1, $`q_1^{(1)}=0`$ and $`q_2^{(1)}=q_1^{(2)}=1`$.

Now consider the evolution of the corresponding semistandard tableaux $`\tau (n)`$, $`n1`$. See Figure 2.

Another look at the algorithm described above should convince the reader that $`\tau (n)`$ is precisely the semistandard tableau obtained when one applies the Robinson-Schensted algorithm, with column insertion, to the word $`a_1\mathrm{}a_n`$.

To see this, look at the tableau $`\tau (17)`$ represented in Figure 2. Recall that $`a_m=i`$ if $`x_i`$ increases by one at time $`m`$, in which case there is a service at the $`i^{th}`$ queue of the first series.

Suppose the next ‘letter’ $`a(18)=2`$. Since $`d_2^{(1)}<d_1^{(1)}`$, that is, $`q_1^{(1)}>0`$, we have a departure from the second queue in the first series, that is, we decrease $`q_1^{(1)}`$ by one and increase $`d_2^{(1)}`$ by one. In turn, this leads to an increase in $`t_2^{(1)}`$, that is, a service at the second queue in the second series, and so, since $`q_1^{(2)}>0`$, we decrease $`q_1^{(2)}`$ by one, and increase $`d_2^{(2)}`$ by one. That’s it, the resulting tableau $`\tau (18)`$ is

| 1 | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 2 | 2 | 2 | 2 | 3 | 3 | 3 |
| 3 | 3 |

and we recognise this procedure as column-insertion of the number 2 into the tableau $`\tau (17)`$.

Note that, now, $`q_1^{(2)}=0`$. Suppose the next letter $`a(19)`$ is also a 2. We still have $`q_1^{(1)}>0`$, so we decrease $`q_1^{(1)}`$ by one and increase $`d_2^{(1)}`$ by one. In turn, this leads to an increase in $`t_2^{(1)}`$, that is, a service at the second queue in the second series; but $`q_1^{(2)}=0`$, so this service is unused and there is no departure (that is, no increase in $`d_2^{(2)}`$). The unused service leads to an increase in $`t_1^{(3)}`$, that is, a service at the only queue in the third series, and we increase $`d_1^{(3)}`$ by one. The resulting tableau $`\tau (19)`$ is

| 1 | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 3 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 2 | 2 | 2 | 2 | 2 | 3 | 3 |
| 3 | 3 |

and, again, we recognise this procedure as column-insertion of the number 2 into the tableau $`\tau (18)`$. And so on.

$`\mathrm{}`$

We will give a completely worked example, starting from an empty tableau, in the next section.

We conclude this section with some remarks on the immediate implications of Theorem 3.1. Let $`l(n)`$ and $`\alpha (n)`$ respectively denote the shape and weight of $`\tau (n)`$. In view of Theorem 3.1, Lemma 2.4 can now be interpreted as stating that $`l_1(n)`$ is the length of the longest non-decreasing subsequence in the reversed word $`a_n\mathrm{}a_1`$. This is a well-known property of the Robinson-Schensted algorithm. Thus, Lemma 2.4 can be regarded as a corollary of Theorem 3.1, or the proof of Lemma 2.4 given in the appendix can be regarded as a new proof of the longest increasing subsequence property of the Robinson-Schensted algorithm.

More generally, we can compare the statement of Theorem 3.1 with Greene’s theorem, and this leads to some remarkable identities. Greene’s theorem (see, for example, ) states that, if $`m_i(n)`$ denotes the maximum of the sum of the lengths of $`i`$ disjoint, non-decreasing subsequences in the reversed word $`a_n\mathrm{}a_1`$, then, for $`ik`$,

$$m_i(n)=l_1(n)+l_2(n)+\mathrm{}+l_i(n).$$
(28)
It therefore follows from Theorem 3.1 that

$$m_i(n)=G_k^{(k)}(n)+G_{k1}^{(k)}(n)+\mathrm{}+G_{ki+1}^{(k)}(n).$$
(29)
It would be interesting to see a direct proof of this identity. Similarly, one can compare Theorem 3.1 with the various extensions of Greene’s theorem given, for example, in .

The implications of Lemma 2.2 for the Robinson-Schensted algorithm would appear to be less well-known. Fix $`k2`$, and set $`H(z)=F^{(k)}(z^{})^{}`$.

###### Corollary 3.2

The weight $`\alpha (n)`$ of $`\tau (n)`$ can be recovered from the sequence of shapes

$$\{\text{ }\text{sh}\text{ }\tau (l),ln\}.$$

In fact, if we set, for $`m0`$,

$$u(m)=\text{ }\text{sh}\text{ }\tau (n+m)\text{ }\text{sh}\text{ }\tau (n),$$

then

$$\alpha (n)=\text{ }\text{sh}\text{ }\tau (n)+H(u).$$

Recall that the recording tableaux $`\sigma (n)`$ are nested; the limiting standard tableau $`\sigma (\mathrm{})=lim_n\mathrm{}\sigma (n)`$ is thus a well-defined object. It follows from Corollary 3.2 that we can recover the ininite word $`a_1a_2\mathrm{}`$ from $`\sigma (\mathrm{})`$.

This is also true for the Robinson-Schensted algorithm applied with row insertion. To see this, recall that the recording tableaux maintained when one applies the row insertion algorithm to the infinite word $`a_1a_2\mathrm{}`$ is the same as that maintained when one applies the column insertion algorithm to the word $`a_1^{}a_2^{}\mathrm{}`$, where $`a_n^{}=ka_n+1`$ (or see, for example, \[18, A.2, Exercise 5\]). We can thus extend the Robinson-Schensted correspondence to a bijective mapping between infinite words and infinite standard tableaux.

## 4 A worked example

Suppose $`k=3`$ and $`n=7`$, and we apply the Robinson-Schensted algorithm with column insertion to the word $`a_1\mathrm{}a_7=3112322`$. We obtain the following sequence of semistandard tableaux:

3

| 1 | 3 |
| --- | --- |

| 1 | 1 | 3 |
| --- | --- | --- |

| 1 | 1 | 3 |
| --- | --- | --- |
| 2 |

| 1 | 1 | 3 |
| --- | --- | --- |
| 2 |
| 3 |

1         1         3          2         2          3

| 1 | 1 | 2 | 3 |
| --- | --- | --- | --- |
| 2 | 2 |
| 3 |

The evolution of the corresponding queueing network is as follows. For each $`n`$, set

$$Q(n)=\left[\begin{array}{cc}q_1^{(1)}(n)& q_2^{(1)}(n)\\ & q_1^{(2)}(n)\end{array}\right]$$

and

$$D(n)=\left[\begin{array}{ccc}d_1^{(1)}(n)& d_2^{(1)}(n)& d_3^{(1)}(n)\\ & d_1^{(2)}(n)& d_2^{(2)}(n)\\ & & d_1^{(3)}(n)\end{array}\right].$$

Initially,

$$Q(0)=\left[\begin{array}{cc}0& 0\\ & 0\end{array}\right]\text{and}D(0)=\left[\begin{array}{ccc}0& 0& 0\\ & 0& 0\\ & & 0\end{array}\right].$$

At time 1, $`a_1=3`$, so there is a service at the third queue in the first series. Since $`q_2^{(1)}(0)=0`$, this queue is empty, and the service is unused, leading to an increase in $`t_2^{(1)}`$ and hence a service at the second queue in the second series. This is also unused, so we have a service at the first (and only) queue in the third series, and there is a departure there: $`d_1^{(3)}(1)=1`$. Thus,

$$Q(1)=\left[\begin{array}{cc}0& 0\\ & 0\end{array}\right]\text{and}D(1)=\left[\begin{array}{ccc}0& 0& 0\\ & 0& 0\\ & & 1\end{array}\right].$$

The corresponding tableau $`\tau (1)`$ is

At time 2, $`a_2=1`$, so there is a service at the first queue in the first series and a customer departs to join the second queue: thus, $`d_1^{(1)}(2)=1`$ and $`q_1^{(1)}(2)=1`$. In the second series, this leads to an increase in $`t_1^{(1)}`$ and hence a departure from the first queue to the second queue: thus, $`d_1^{(2)}(2)=1`$ and $`q_1^{(2)}(2)=1`$. In turn, this leads to an increase in $`t_1^{(2)}`$ and hence a service at the only queue in the third series, which yields a (second) departure from that queue and we have $`d_1^{(3)}(2)=2`$. Thus,

$$Q(2)=\left[\begin{array}{cc}1& 0\\ & 1\end{array}\right]\text{and}D(2)=\left[\begin{array}{ccc}1& 0& 0\\ & 1& 0\\ & & 2\end{array}\right].$$

The corresponding tableau $`\tau (2)`$ is

| 1 | 3 |
| --- | --- |

Similarly, at time 3, $`a_3=1`$, and we get

$$Q(3)=\left[\begin{array}{cc}2& 0\\ & 2\end{array}\right]\text{and}D(3)=\left[\begin{array}{ccc}2& 0& 0\\ & 2& 0\\ & & 3\end{array}\right].$$

The corresponding tableau $`\tau (3)`$ is

| 1 | 1 | 3 |
| --- | --- | --- |

At time 4, $`a_4=2`$, and there is a departure from the second queue in the first series. This provides a service at the second queue in the second series, which is non-empty, so we have a departure from that queue as well. Thus,

$$Q(4)=\left[\begin{array}{cc}1& 1\\ & 1\end{array}\right]\text{and}D(4)=\left[\begin{array}{ccc}2& 1& 0\\ & 2& 1\\ & & 3\end{array}\right].$$

The corresponding tableau $`\tau (4)`$ is

| 1 | 1 | 3 |
| --- | --- | --- |
| 2 |

At time 5, there is a service at the third queue in the first series, and a customer departs. That’s all.

$$Q(5)=\left[\begin{array}{cc}1& 0\\ & 1\end{array}\right]\text{and}D(5)=\left[\begin{array}{ccc}2& 1& 1\\ & 2& 1\\ & & 3\end{array}\right].$$

The corresponding tableau $`\tau (5)`$ is

| 1 | 1 | 3 |
| --- | --- | --- |
| 2 |
| 3 |

At time 6, there is a service at the second queue in the first series, and a customer departs; this yields a service at the second queue in the second series and a customer departs from there also.

$$Q(6)=\left[\begin{array}{cc}0& 1\\ & 0\end{array}\right]\text{and}D(6)=\left[\begin{array}{ccc}2& 2& 1\\ & 2& 2\\ & & 3\end{array}\right].$$

The corresponding tableau $`\tau (6)`$ is

| 1 | 1 | 3 |
| --- | --- | --- |
| 2 | 2 |
| 3 |

At time 7, there is a service at the second queue in the first series, but this queue is empty and it is not used; this yields a service at the first queue in the second series, leading to a departure from that queue and consequently a service at (and departure from) the first (and only) queue in the third series.

$$Q(7)=\left[\begin{array}{cc}0& 1\\ & 1\end{array}\right]\text{and}D(7)=\left[\begin{array}{ccc}2& 2& 1\\ & 3& 2\\ & & 4\end{array}\right].$$

The final tableau $`\tau (7)`$ is

| 1 | 1 | 2 | 3 |
| --- | --- | --- | --- |
| 2 | 2 |
| 3 |

## 5 Random walk in a Weyl chamber

In this section we record some properties of the conditioned walk of Theorem 1.1, and extend its definition beyond the case $`p_1<\mathrm{}<p_k`$.

The random walk $`X`$ is a Markov chain on $`_+^k`$ with $`X(0)=o`$ and transition matrix

$$P(x,y)=p^{yx}1_{\{yxb\}}.$$

Denote by $`P_x`$ the law of the walk started at $`xW_+^k`$.

We will refer to the random walk with $`p_1=\mathrm{}=p_k`$ as the homogeneous walk.

Denote by $`s_l`$ the Schur polynomial associated with the integer partition $`l_1l_2\mathrm{}l_k0`$.

###### Lemma 5.1

For any $`r𝒫_k`$, the function $`h_r:_+^k`$, defined by

$$h_r(x)=p^xs_x^{}(r)1_{xW},$$

is harmonic for $`P`$. Note that $`h_r`$ is strictly positive on $`W_+^k`$.

Proof. This follows immediately from the identity

$$\underset{i}{}s_{l+e_i}(r)=s_l(r),$$

which in turn can be seen as a special case of the Weyl character formula, or verified directly using the formula

$$s_l(p)=det\left(p_i^{l_j+kj}\right)/det\left(p_i^{kj}\right).$$

$`\mathrm{}`$

###### Lemma 5.2

Suppose $`0<p_1<\mathrm{}<p_k`$. Then, for any $`xW_+^k`$,

$$P_x(X(n)W,\text{ for all }n0)=Cp^xs_x^{}(p),$$

where $`C`$ is a constant independent of $`x`$. In particular, the transition matrix associated with the conditioned walk of Theorem 1.1 is given by

$$\widehat{P}(x,y)=\frac{p^ys_y^{}(p)}{p^xs_x^{}(p)}P(x,y)=\frac{s_y^{}(p)}{s_x^{}(p)}1_{\{yxb\}}.$$
(30)
Proof. When $`r=p`$, the Doob transform of the random walk $`X`$ via the harmonic function $`h_r`$ has transition matrix $`\widehat{P}`$. Note that this can also be regarded as the Doob transform of the homogeneous walk via the function $`xs_x^{}(kp)`$. It follows from the asymptotic analysis of the Green function associated with the (Poissonized) homogeneous walk presented in  that, if $`\kappa (x,y)`$ is the Martin kernel associated with the homogeneous walk, then

$$\kappa (x,y)\text{constant}\times s_x^{}(kp)$$

whenever $`y`$ tends to infinity in $`W`$ in the direction $`p`$. Thus, by standard Doob-Hunt theory (see, for example, ), any realisation of the corresponding Doob transform, starting from the origin $`o`$, almost surely goes to infinity in the direction $`p`$. Moreover, any Doob transform on $`W`$ which almost surely goes to infinity in the direction $`p`$ is necessarily the same Doob transform. It therefore suffices to show that the ‘properly’ conditioned walk of Theorem 1.1, which is the Doob transform of $`X`$ via the harmonic function

$$g(x)=P_x(X(n)W,\text{ for all }n0),$$

almost surely goes to infinity in the direction $`p`$. But this follows immediately from the estimate, denoting the law of the conditioned walk by $`\widehat{P}`$,

$$\widehat{P}(|X(n)pn|>ϵn)P(|X(n)pn|>ϵn)/g(x)Ke^{c(ϵ)n}/g(x),$$

where $`c(ϵ)>0`$, and a standard Borel-Cantelli argument. $`\mathrm{}`$

Note that the transition matrix $`\widehat{P}`$ is well-defined by (30) for any $`p𝒫_k`$ and, by the symmetry of the Schur polynomials, is symmetric in the $`p_i`$.

The proof of Lemma 5.2 given above is presented in more detail in , where an explicit formula for the constant $`C`$ is also given.

## 6 The Robinson-Schensted algorithm with random words

Having made the connection between the path-transformation $`G^{(k)}`$ and the Robinson-Schensted algorithm, we will now give a direct proof of Theorem 1.1, purely in the latter context. In fact, we will present a more general result, which does not require the condition $`p_1<\mathrm{}<p_k`$.

Let $`\xi _1,\xi _2,\mathrm{}`$ be a sequence of independent random variables with common distribution $`p𝒫_k`$. Let $`(S(n),T(n))`$ be the pair of semistandard and standard tableaux associated, by the Robinson-Schensted correspondence (with column-insertion), with the random word $`\xi _1\xi _2\mathrm{}\xi _n`$. Here, $`T(n)`$ is the recording tableau. Denote the shape of $`S(n)`$ by $`\lambda (n)`$; the weight (or type) of $`S(n)`$ is $`X(n)`$, where

$$X_i(n)=|\{1mn:\xi _m=i\}|.$$

Note that $`X`$ is the random walk discussed throughout this paper, with transition matrix

$$P(x,y)=p^{yx}1_{\{yxb\}}.$$

The joint law of $`(S(n),T(n))`$ is given, for $`\text{ sh }\sigma =\text{ sh }\tau n`$, by

$$P(S(n)=\sigma ,T(n)=\tau )=p^\sigma ,$$
(31)
and, for $`xC=\{x_+^k:x_1\mathrm{}x_k\}`$,

$$P(\lambda (n)=x)=s_x(p)f_x.$$

Here $`p^\sigma `$ is shorthand for $`p^a`$, where $`a`$ is the weight of the tableau $`\sigma `$, and $`f_x`$ is the number of standard tableaux with shape $`x`$. The formula (31) follows immediately from the fact that the Robinson-Schensted correspendence with column-insertion, as in the case with row-insertion, is bijective.

Consider the Doob transform of $`P`$ on $`C`$, defined by its transition matrix

$$Q(x,y)=\frac{p^ys_y(p)}{p^xs_x(p)}P(x,y)=\frac{s_y(p)}{s_x(p)}1_{\{yxb\}}.$$
(32)
###### Theorem 6.1

$`\lambda `$ is a Markov chain on $`C`$ with transition matrix $`Q`$.

Proof. For $`x,yC`$, we will write $`xy`$ if $`yxb`$. Recall that a standard tableau $`\tau `$ with entries $`\{1,2,\mathrm{},n\}`$ can be identified with a sequence of integer partitions

$$l(1)l(2)\mathrm{}l(n)$$

where $`l(m)`$ is the shape of the subtableau of $`\tau `$ consisting only of the entries $`\{1,2,\mathrm{},m\}`$. Since $`T(n)`$ is a recording tableau, it is identified in this way with the sequence

$$\lambda (1)\lambda (2)\mathrm{}\lambda (n).$$

Thus, summing (31) over semistandard tableaux $`\sigma `$ with a given shape $`l(n)n`$, we obtain

$$P(\lambda (1)=l(1),\mathrm{},\lambda (n)=l(n))=\underset{\text{ sh }\sigma =l(n)}{}p^\sigma =s_{l(n)}(p),$$
(33)
and so, for $`xyn+1`$,

$`P(\lambda (n+1)=y|\lambda (1)=l(1),\mathrm{},\lambda (n1)=l(n1),\lambda (n)=x)`$
$`=`$ $`{\displaystyle \frac{P(\lambda (1)=l(1),\mathrm{},\lambda (n1)=l(n1),\lambda (n)=x,\lambda (n+1)=y)}{P(\lambda (1)=l(1),\mathrm{},\lambda (n1)=l(n1),\lambda (n)=x)}}`$
$`=`$ $`{\displaystyle \frac{s_y(p)}{s_x(p)}},`$
as required. $`\mathrm{}`$

Recalling the connection between $`G^{(k)}`$ and the Robinson-Schensted algorithm described in the previous section, and comparing $`Q`$ with the transition matrix $`\widehat{P}`$ defined by (30), we deduce the following generalisation of Theorem 1.1.

###### Corollary 6.2

$`\widehat{X}=G^{(k)}(X)`$ is a Markov chain on $`W_+^k`$ with transition matrix $`\widehat{P}`$.

We will now record two lemmas which will yield an explicit description of the joint law of $`X`$ and $`\widehat{X}`$, and an intertwining relationship between their respective transition matrices.

Denote by $`\kappa _{xy}`$ the number of tableaux of shape $`x`$ and weight $`y`$. (These are the Kostka numbers.)

###### Lemma 6.3

$$P(X(n)=y|\lambda (m),mn)=K(\lambda (n),y),$$
(34)
where

$$K(x,y)=\frac{p^y}{s_x(p)}\kappa _{xy}.$$
(35)
Proof. First note that the $`\sigma `$-algebra generated by $`\{\lambda (m),mn\}`$ is precisely the same as the $`\sigma `$-algebra generated by $`T(n)`$. Thus, the conditional law of $`X(n)`$, given $`\{\lambda (m),mn\}`$, is the same as the conditional law of $`X(n)`$, given $`T(n)`$. But this only depends on the shape, $`\lambda (n)`$, of $`T(n)`$, and is given by

$$K(x,y):=P(X(n)=y|\lambda (n)=x)=\frac{p^y}{s_x(p)}\kappa _{xy},$$

as required. $`\mathrm{}`$

We will now show that $`P`$ and $`Q`$ are intertwined via the Markov kernel $`K`$, that is:

###### Lemma 6.4

$`QK=KP`$.

Proof.

$`(QK)(x,z)`$ $`=`$ $`{\displaystyle \underset{yC}{}}Q(x,y)K(y,z)`$
$`=`$ $`{\displaystyle \underset{yC}{}}P(x,y){\displaystyle \frac{p^ys_y(p)}{p^xs_x(p)}}{\displaystyle \frac{p^z}{s_y(p)}}\kappa _{yz}`$
$`=`$ $`{\displaystyle \underset{i}{}}p_ip^xp^{xe_i}{\displaystyle \frac{p^z}{s_x(p)}}\kappa _{x+e_i,z}`$
$`=`$ $`{\displaystyle \frac{p^z}{s_x(p)}}{\displaystyle \underset{i}{}}\kappa _{x+e_i,z}.`$
On the other hand,

$`(KP)(x,z)`$ $`=`$ $`{\displaystyle \underset{y}{}}K(x,y)P(y,z)`$
$`=`$ $`{\displaystyle \underset{i}{}}K(x,ze_i)p_i`$
$`=`$ $`{\displaystyle \underset{i}{}}p_i{\displaystyle \frac{p^{ze_i}}{s_x(p)}}\kappa _{x,ze_i}`$
$`=`$ $`{\displaystyle \frac{p^z}{s_x(p)}}{\displaystyle \underset{i}{}}\kappa _{x,ze_i}.`$
The statement of the lemma now follows from the identity

$$\underset{i}{}\kappa _{x+e_i,z}=\underset{i}{}\kappa _{x,ze_i};$$

to see that this holds, observe that, for any $`q_+^k`$,

$$\underset{z}{}q^z\underset{i}{}\kappa _{x+e_i,z}=|q|s_x(q)=\underset{z}{}q^z\underset{i}{}\kappa _{x,ze_i}.$$

$`\mathrm{}`$

###### Corollary 6.5

If we set $`J(x,y)=K(x^{},y)`$, then

$$P(X(n)=y|\widehat{X}(m),mn,\widehat{X}(n)=x)=J(x,y)$$
(36)
and $`\widehat{P}J=JP`$.

For a discussion on the role of intertwining in the context of Pitman’s $`2MX`$ theorem (the case $`k=2`$), see .

It is instructive to note that Theorem 6.1 also follows from Lemmas 6.3 and 6.4, provided we can show that there is a class of functions of the form $`K\phi `$, $`\phi :_+^k`$, which separate probability distributions on $`C`$. Indeed, by Lemmas 6.3 and 6.4,

$`E\left[(K\phi )(\lambda (n+1))|\lambda (m),mn\right]`$
$`=`$ $`E\left[E\left[\phi (X(n+1))|\lambda (n+1)\right]|\lambda (m),mn\right]`$
$`=`$ $`E\left[E\left[\phi (X(n+1))|\lambda (m),mn+1\right]|\lambda (m),mn\right]`$
$`=`$ $`E\left[\phi (X(n+1))|\lambda (m),mn\right]`$
$`=`$ $`{\displaystyle \underset{y}{}}K(\lambda (n),y)E\left[\phi (X(n+1))|X(n)=y\right]`$
$`=`$ $`{\displaystyle \underset{y}{}}K(\lambda (n),y){\displaystyle \underset{z}{}}P(y,z)\phi (z)`$
$`=`$ $`[(KP)\phi ](\lambda (n))`$
$`=`$ $`[(QK)\phi ](\lambda (n))`$
$`=`$ $`[Q(K\phi )](\lambda (n))`$
which would imply that $`\lambda `$ is a Markov chain with transition matrix $`Q`$ if the functions $`K\phi `$ were determining. To find such a class of functions, we recall that the matrix

$$\{\kappa _{xy},(x,y)C^2\}$$

is invertible (see, for example, ). Thus, if we set, for $`q_+^k`$,

$$\phi _q(y)=p^y\underset{zC}{}\kappa _{yz}^{(1)}q^zs_z(p)1_{\{yC\}},$$
(37)
we have $`(K\phi _q)(x)=q^x`$, and these functions are clearly determining.

By exactly the same arguments as those given in the proof of Theorem 6.1, if $`\mu (n)`$ denotes the shape of the tableau obtained by applying the Robinson-Schensted algorithm with row insertion to the random word $`\xi _1\mathrm{}\xi _n`$, we obtain:

###### Theorem 6.6

$`\mu `$ is a Markov chain on $`C`$ with transition matrix $`Q`$.

## 7 Poissonized version

We will now define a continuous version of $`G^{(k)}`$, and state Poissonized versions of Corollaries 6.2 and 6.5. This is an interesting setting in its own right, as the conditioned walk in this case is closely related to the Charlier ensemble and process (see, for example, ), but more importantly it provides a convenient framework in which to apply Donsker’s theorem and obtain the Brownian analogue of Corollary 6.2, as was presented in  in the case $`p=(1/k,\mathrm{},1/k)`$. Moreover, given the connection we have now made with the Robinson-Schensted algorithm, this continuous path transformation can also be regarded as a continuous analogue of the Robinson-Schensted algorithm (see section 10 for further remarks in this direction).

Let $`D_0(_+)`$ denote the space of cadlag paths $`f:_+`$ with $`f(0)=0`$. We will extend the definition of the operations $``$ and $``$ to a continuous context. For $`f,gD_0(_+)`$, define $`fgD_0(_+)`$ and $`fgD_0(_+)`$ by

$$(fg)(t)=\underset{0st}{inf}[f(s)+g(t)g(s)],$$
(38)
and

$$(fg)(t)=\underset{0st}{sup}[f(s)+g(t)g(s)].$$
(39)
As in the discrete case, these operations are not associative: unless otherwise deleniated by parentheses, the default order of operations is from left to right; for example, when we write $`fgh`$, we mean $`(fg)h`$.

Define a sequence of mappings $`\mathrm{\Gamma }^{(k)}:D_0(_+)^kD_0(_+)^k`$ by

$$\mathrm{\Gamma }^{(2)}(f,g)=(fg,gf),$$
(40)
and, for $`k>2`$,

$`\mathrm{\Gamma }^{(k)}(f_1,`$ $`\mathrm{},f_k)=(f_1f_2\mathrm{}f_k,`$
$`\mathrm{\Gamma }^{(k1)}(f_2f_1,f_3(f_1f_2),\mathrm{},f_k(f_1\mathrm{}f_{k1}))).`$ (41)
Let $`N=(N_1,\mathrm{},N_k)`$ be a continuous-time random walk with generator $`Gf(x)=_i\mu _i[f(x+e_i)f(x)].`$ Denote by $`_x`$ the law of $`N`$ started from $`x`$, and by $`(R_t)`$ the corresponding semigroup. For convenience, we will also denote the corresponding transition kernel by $`R_t(x,y)`$. Set $`p_i=\mu _i/|\mu |`$, and denote by $`𝕊_x`$ the law of the $`h_p`$-transform on $`W`$, started at $`x`$, and the corresponding semigroup by $`S_t`$.

Note that the embedded discrete-time random walk in $`N`$ has the same law as $`X`$. That is, if $`\tau _n=inf\{t0:|N(t)|=n\}`$ and $`Y(n)=N(\tau _n)`$, then $`Y`$ is a random walk on $`_+^k`$ with transition matrix $`P`$.

###### Theorem 7.1

The law of $`M=\mathrm{\Gamma }^{(k)}(N)`$ under $`_o`$ is the same as the law of $`N`$ under $`𝕊_o`$.

Moreover, if $`J`$ is the Markov kernel defined in the previous section, then:

###### Theorem 7.2

$$_o(N(t)=y|M(s),st)=J(M(t),y)$$
(42)
and for $`t0`$, $`S_tJ=JR_t`$.

## 8 Brownian motion in a Weyl chamber and random matrices

Let $`X`$ be a standard Brownian motion in $`^d`$, and let $`_x`$ denote the law of $`X`$ started at $`x`$. Denote the corresponding semigroup and transition kernel by $`(P_t)`$, and the natural filtration of $`X`$ by $`(_t)`$.

Recall that

$$W=\{x^d:x_1\mathrm{}x_d\}$$

and denote by $`\stackrel{~}{P}_t`$ the semigroup of the process killed at the first exit time

$$T=inf\{t0:X(t)W\}.$$

Define $`_x`$, for $`xW^{}`$, by

$$_x|__t=\frac{h(X(tT))}{h(x)}_x|__t,$$

where $`h`$ is the Vandermonde function $`h(x)=_{i<j}(x_jx_i)`$. Denote the corresponding semigroup by $`Q_t`$.

The measure

$$_o=\underset{W^{}x0}{lim}_x$$

is well-defined, and can be interpreted as the law of the eigenvalue-process associated with Hermitian Brownian motion . The law of $`X(1)`$ under $`_o`$ is the familiar Gaussian Unitary Ensemble (GUE) of random matrix theory.

In  it was shown, by applying Donsker’s theorem in the context of Theorem 7.1 with $`\mu =(1,\mathrm{},1)`$, that:

###### Theorem 8.1

The law of $`\mathrm{\Gamma }^{(d)}(X)`$ under $`_o`$ is the same as the law of $`X`$ under $`_o`$.

In particular<sup>1</sup><sup>1</sup>1See remark 2(ii) in section 10 below, $`(X_d\mathrm{}X_1)(1)`$ has the same law as the largest eigenvalue of a $`d\times d`$ GUE random matrix; this had been observed earlier by Baryshnikov  and by Gravner, Tracy and Widom . A similar representation was obtained in .

Here we record some additional properties of the process $`R=\mathrm{\Gamma }^{(d)}(X)`$, and its relationship with $`X`$, which are inherited, in the same application of Donsker’s theorem, from Theorem 7.2.

###### Theorem 8.2

$$_o(X(t)dx|R(s),st;R(t)=r)=L(r,dx),$$
(43)
where $`L`$ is characterised by

$$_^ke^{\lambda y}L(x,dy)=\frac{det(e^{\lambda _ix_j})}{h(\lambda )h(x)}=:c_\lambda (x).$$
(44)
Also, for $`t0`$, $`Q_tL=LP_t`$.

The intertwining $`Q_tL=LP_t`$ can also be seen as a direct consequence of the Harish-Chandra/Itzykson-Zuber formula  for the Laplace transform of the conditional law of the diagonal of a GUE random matrix given its eigenvalues, using the fact that the diagonal of a Hermitian Brownian motion evolves according to the semigroup $`P_t`$ and the eigenvalues evolve according to the semigroup $`Q_t`$. It is also easily verified using the Karlin-MacGregor formula

$$\stackrel{~}{P}_t(x,y)=det(P_t(x_i,y_j)).$$

We will now present analogous results for Brownian motion with drift. Fix $`\mu ^d`$, and denote by $`_x^{(\mu )}`$ the law of Brownian motion in $`^d`$ with drift $`\mu `$. Denote by $`(P_t^{(\mu )})`$ the corresponding semigroup and by $`(\stackrel{~}{P}_t^{(\mu )})`$ the semigroup of the process killed at the first exit time $`T`$ of the Weyl chamber $`W`$. Define $`h_\mu `$ by

$$h_\mu (x)=e^{\mu x}det\left(e^{\mu _ix_j}\right).$$
(45)
It is easy to check directly that $`h_\mu `$ a positive harmonic function for $`\stackrel{~}{P}_t^{(\mu )}`$. Define

$$_x^{(\mu )}|__t=\frac{h_\mu (X(tT))}{h_\mu (x)}_x^{(\mu )}|__t.$$

Denote the corresponding semigroup by $`Q_t^{(\mu )}`$. Recalling the absolute continuity relationship

$$\stackrel{~}{P}_t^{(\mu )}(x,y)=e^{\mu (yx)|\mu |^2t/2}\stackrel{~}{P}_t(x,y),$$
(46)
we can write

$$Q_t^{(\mu )}(x,y)=\frac{h_\mu (y)}{h_\mu (x)}\stackrel{~}{P}_t^{(\mu )}(x,y)=\frac{det\left(e^{\mu _iy_j}\right)}{det\left(e^{\mu _ix_j}\right)}e^{|\mu |^2t/2}\stackrel{~}{P}_t(x,y),$$
(47)
and we note that this is symmetric in the $`\mu _i`$.

It is easy to verify that measure

$$_o^{(\mu )}=\underset{W^{}x0}{lim}_x^{(\mu )}$$

is well-defined.

Applying Donskers theorem in the context of Theorem 7.1, as in , we obtain:

###### Theorem 8.3

The law of $`\mathrm{\Gamma }^{(d)}(X)`$ under $`_o^{(\mu )}`$ is the same as the law of $`X`$ under $`_o^{(\mu )}`$.

As in the discrete case, we remark that the law $`_o^{(\mu )}`$ is symmetric in the drifts $`\mu _i`$.

We also have, by the same application of Donsker’s theorem, the following analogue of Theorem 7.2.

###### Theorem 8.4

$$_o^{(\mu )}(X(t)dx|R(s),st;R(t)=r)=L^{(\mu )}(r,dx),$$
(48)
where

$$L^{(\mu )}(x,dy)=c_\mu (x)^1e^{\mu y}L(x,dy).$$
(49)
Also, for $`t0`$,

$$Q_t^{(\mu )}L^{(\mu )}=L^{(\mu )}P_t^{(\mu )}.$$
(50)
The intertwining relationship (50) can also be verified directly using $`Q_tL=LP_t`$ and (46).

For related work on reflecting Brownian motions and non-colliding diffusions see  and references therein.

## 9 An application in queueing theory

In this section, using the connection with the Robinson-Schensted correspondence obtained in Section 3, we will write down a formula for the ‘transient distribution’ of a series of $`M/M/1`$ queues in tandem. There are many papers on this topic for the case of a single queue, where the solution is given in terms of modified Bessel functions; see  and references therein. In , the case of two queues was considered and a solution obtained, but the techniques used there do not seem to extend easily to higher dimensions.

Consider a series of $`M/M/1`$ queues in tandem, $`k`$ in number, driven by Poisson processes $`N_1,\mathrm{},N_k`$ with respective intensities $`\mu _1,\mathrm{},\mu _k`$. The first queue has infinitely many customers, and the remaining queues are initially empty. At every point of $`N_i`$, there is a service at the $`i^{th}`$ queue and, provided that queue is not empty, a customer departs and joins the $`(i+1)^{th}`$ queue (or leaves the system if $`i=k`$).

Denote by $`D(t)=(D_1(t),\mathrm{},D_k(t))`$ the respective numbers of customers to depart from each queue up to time $`t`$. Note that, since there are always infinitely many customers in the first queue, $`D_1`$ is a Poisson process; we can thus ignore the first queue, think of the second queue as the first in a series of $`k1`$ queues, and think of $`D_1`$ as the arrival process at the first of these $`k1`$ queues in series. This is a more conventional set up in queueing theory. The state of the system is described by the queue-lengths

$$Q_1=D_1D_2,\mathrm{},Q_{k1}=D_{k1}D_k.$$
(51)
We will write down a formula for the law of $`D(t)`$ which, in turn, yields the law of $`Q(t)=(Q_1(t),\mathrm{},Q_{k1}(t))`$.

Without loss of generality we can assume that $`|\mu |=1`$. The de-Poissonized version of this problem is to consider the usual random walk $`X`$, with $`p=\mu `$, and consider the law of $`\delta (n)=(D^{(k)}(X))(n)`$. But we know this law, from sections 3 and 6. It is the law of $`\beta (S(n))`$, where $`S(n)`$ of the random semistandard tableau obtained when one applies the Robinson-Schensted algorithm with column-insertion to the random word $`\xi _1\mathrm{}\xi _k`$ and $`\beta _i(\tau )`$ denotes the number of $`i`$’s in the $`i^{th}`$ row of a tableau $`\tau `$.

Thus,

$$P(D(t)=d)=e^t\underset{n0}{}\frac{t^n}{n!}P(\delta (n)=d),$$
(52)
where

$$P(\delta (n)=d)=\underset{ld,ln}{}\underset{\text{ sh }\tau =l}{}p^\tau f_l1_{\{\beta (\tau )=d\}}.$$
(53)
This formula is complicated in general but simplifies in certain cases.

Consider the case $`k=2`$. In this case, we have only one summand:

$$P(\delta (n)=d)=p_1^{d_1}p_2^{nd_1}f_{(nd_2,d_2)}.$$
(54)
By the hook-length formula (see, for example, ), for $`nd_1+d_2`$,

$$f_{(nd_2,d_2)}=n!\frac{n2d_2+1}{(nd_2+1)!d_2!}.$$

Thus, recalling that $`p=\mu `$,

$$P(D(t)=d)=e^t\underset{nd_1+d_2}{}t^n\mu _1^{d_1}\mu _2^{nd_1}\frac{n2d_2+1}{(nd_2+1)!d_2!}.$$
(55)
It follows that

$$P(Q(t)=q)=(\mu _1/\mu _2)^qe^t\underset{mq}{}(m+1)(\mu _2t)^mI_{m+1}(2\sqrt{\mu _1\mu _2}t).$$
(56)
Let $`s_{l/d}`$ denote the Schur polynomial associated with the skew-tableau $`l/d`$ (see, for example, ). We will use the following formula:

$$\underset{l}{}s_{l/d}(x)\frac{t^{|l|}f_l}{|l|!}=e^{|x|t}\frac{t^{|d|}f_d}{|d|!}.$$
(57)
This follows from the identity

$$\underset{l}{}s_{l/d}(x)s_l(y)=s_d(y)\underset{i,j}{}(1x_iy_j)^1$$
(58)
(this is a variant of Cauchy’s identity; see, for example, \[31, pp62-70\]) and the fact that

$$\underset{n\mathrm{}}{lim}s_l\left(\frac{t}{n}.1^n\right)=\frac{t^{|l|}f_l}{|l|!}.$$
(59)
In the case $`k=3`$, if $`p_2=p_3`$, we have

$`P(D_1(t)=d_1,D_2d_2,D_3(t)=d_3)`$ $`=`$ $`e^tp^d{\displaystyle \underset{l}{}}s_{l/d}(p_2,p_3){\displaystyle \frac{t^{|l|}f_l}{|l|!}}`$ (60)
$`=`$ $`e^{p_1t}p^d{\displaystyle \frac{t^{|d|}f_d}{|d|!}}.`$
It would be interesting to compare (60) with the explicit formulas obtained in  for this case.

In the general case, we can simplify the formula (52) if $`d`$ is constant. Suppose $`d_i=m`$ for all $`i`$. Then, using (57) and the hook-length formula,

$`P(D(t)=d)`$ $`=`$ $`e^tp^d{\displaystyle \underset{l}{}}s_{l/d}(p_2,p_3,\mathrm{},p_k){\displaystyle \frac{t^{|l|}f_l}{|l|!}}`$ (61)
$`=`$ $`e^{p_1t}p^d{\displaystyle \frac{t^{|d|}f_d}{|d|!}}`$ (62)
$`=`$ $`e^{p_1t}{\displaystyle \underset{i}{}}p_i^mt^{mk}{\displaystyle \frac{G(k+l)}{G(k)G(l)}},`$ (63)
where $`G`$ is Barne’s function, defined by $`G(k)=_{ik}\mathrm{\Gamma }(i)`$.

## 10 Concluding remarks

1. The Krawchouk process: A binomial version of Theorem 1.1 was presented in . This states that, if $`X`$ is a random walk in $`Z_+^k`$ with transition matrix

$$P(x,y)=Cp^{yx}1_{yx\{0,1\}^k}$$

($`C`$ is a normalising constant) then, assuming $`p_1<\mathrm{}<p_k`$ and extending slightly the domain of $`G^{(k)}`$, $`G^{(k)}(X)`$ has the same law as that of $`X`$ conditioned to stay forever in $`W`$. In this case, a similar connection can be made with the dual Robinson-Schensted-Knuth (RSK) correspondence for zero-one matrices and analogues of all the main results of Section 6 can be obtained similarly. The Schur polynomials again play an important role. See  for details.

2. Properties of $`\mathrm{\Gamma }^{(k)}`$: The following continuous analogues of Lemmas 2.1-2.4 can be readily verified. Denote by $`C_0(_+,^k)`$ the set of continuous functions $`f:_+^k`$ with $`f(0)=o`$. For $`fC_0(_+,^k)`$, where $`k2`$,

* $`|\mathrm{\Gamma }^{(k)}(f)|=|f|`$
* $`\mathrm{\Gamma }_k^{(k)}(f)=f_k\mathrm{}f_1`$
* $`f(t)=[\mathrm{\Gamma }^{(k)}(f)](t)+\mathrm{\Phi }^{(k)}([\mathrm{\Gamma }^{(k)}(f)](t,u),ut),`$ where $`\mathrm{\Phi }^{(k)}`$ is defined on a suitable domain as the continuous analogue of $`F^{(k)}`$.

In this continuous setting, the identity (ii) can be verified directly using the ‘sup-integration by parts’ formula

$$\underset{0<s<t}{sup}\left\{\underset{0<r<s}{sup}u(r)+v(s)\right\}\underset{0<s<t}{sup}\left\{u(s)+\underset{0<r<s}{sup}v(r)\right\}$$

$$=\underset{0<s<t}{sup}u(s)+\underset{0<s<t}{sup}v(s),$$

for $`u,vC_0(_+,^k)`$. This is a ‘max-plus’ analogue of the usual integration by parts formula and is easily verified by the method of Laplace.

3. A continuous Robinson-Schensted algorithm: Given the connection we have made between the path-transformations $`G^{(k)}`$ and the Robinson-Schensted algorithm, the mappings $`\mathrm{\Gamma }^{(k)}`$ can be used to define a continuous version of the Robinson-Schensted algorithm. More precisely, let $`𝒞_{GC}`$ denote the Gelfand-Cetlin cone, which consists of triangular arrays of real numbers

$$(x_j^{(i)},1ik,1ji)$$
(64)
satisfying $`x_j^{(i)}x_j^{(i1)}x_{j+1}^{(i)}`$, for all $`i,j`$. Points in the Gelfand-Cetlin cone can be regarded as continuous analogues of semistandard tableaux. The continuous analogue of a word is a continuous function $`f:[0,1]^k`$ with $`f(0)=o`$: denote the set of these functions by $`C_0([0,1],^k)`$. Define a map $`\varphi :C_0([0,1],^k)𝒞_{GC}`$, as follows. For convenience, let $`\mathrm{\Gamma }^{(1)}`$ be the identity transformation. If we set $`x=\varphi (f_1,\mathrm{},f_k)`$ then, for each $`1ik`$,

$$x^{(i)}=([\mathrm{\Gamma }_i^{(i)}(f_1,\mathrm{},f_i)](1),\mathrm{},[\mathrm{\Gamma }_1^{(i)}(f_1,\mathrm{},f_i)](1)).$$
(65)
The continuous analogue of the corresponding ‘recording tableau’ is the path

$$\rho (f)=\{[\mathrm{\Gamma }^{(k)}(f)](t),0t1\}C_0([0,1],W).$$
(66)
By analogy with the discrete Robinson-Schensted algorithm, the function $`f`$ can be uniquely recovered from the pair $`\varphi (f)`$ and $`\rho (f)`$. A more detailed discussion on the properties of this continuous Robinson-Schensted algorithm will be presented elsewhere.

4. GUE minors: Let $`A`$ be a $`k\times k`$ GUE random matrix and denote the eigenvalues of the $`i^{th}`$ minor $`(A_{lm},l,mi)`$ by $`\lambda _1^{(i)}\mathrm{}\lambda _i^{(i)}`$, for $`ik`$. In the above context, Baryshnikov  showed that, if $`(B(t),0t1)`$ is a standard Brownian motion in $`^k`$, then the random vector

$$(\varphi _1^{(1)}(B),\mathrm{},\varphi _1^{(k)}(B))$$

has the same law as

$$(\lambda _1^{(1)},\mathrm{},\lambda _1^{(k)}).$$

In , Donsker’s theorem is applied in the context of a random semistandard tableau with the same law as $`T(n)`$ of section 6 in the homogeneous case $`p_1=\mathrm{}=p_k`$. We can thus extend Baryshnikov’s arguments using the the representation for the Robinson-Schensted algorithm given in this paper and the continuity of the mappings $`\mathrm{\Gamma }^{(i)}`$, $`ik`$, to see that, in fact, $`\varphi (B)`$ has the same law as

$$(\lambda ^{(1)},\mathrm{},\lambda ^{(k)}).$$

However, it is easy to see<sup>2</sup><sup>2</sup>2Bougerol and Jeulin, private communication, by considering the case $`k=2`$, that these identities do not extend to the process level (that is, with $`\varphi `$ defined simultaneously on intervals $`[0,t]`$ instead of just $`[0,1]`$ and ‘GUE’ replaced by ‘Hermitian Brownian motion’).

5. Related topics: The intertwining of Lemma 6.4 is closely related to the work of Biane on quantum random walks . The Robinson-Schensted correspondence is of fundamental importance to the representation theory of $`S_n`$ and $`GL(n)`$. Related topics in representation theory (which are certainly connected to results presented in this paper) include Littelmann’s path model for the finite-dimensional representations of $`GL(n)`$ (see, for example, ), crystal bases and representations of quantum groups (see, for example, ).

## Appendix

Proof of Lemma 2.1: The first identity is trivial:

$`(yx)(n)`$ $`=`$ $`\underset{0mn}{\mathrm{max}}[y(m)+x(n)x(m)]`$
$`=`$ $`x(n)+y(n)+\underset{0mn}{\mathrm{max}}[y(m)y(n)x(m)]`$
$`=`$ $`x(n)+y(n)(xy)(n).`$
If we set $`z=yx`$, and $`s(n)=\mathrm{max}_{0mn}z(n)`$, then the second identity is equivalent to the well-known fact that

$$s(n)=\underset{ln}{\mathrm{min}}[2s(l)z(l)].$$

$`\mathrm{}`$

Proof of Lemma 2.2: Fix $`x\mathrm{\Lambda }_k`$, and write $`G^{(k)}=G^{(k)}(x)`$ unless otherwise indicated. Similarly for $`D^{(k)}`$ and $`T^{(k)}`$. We will first show that $`|G^{(k)}|=|x|`$. We will prove this by induction on $`k`$. The case $`k=2`$ is given by Lemma 2.1. Assume the induction hypothesis for $`k1`$. We recall from the definitions that

$$G^{(k)}=(D_k^{(k)},G^{(k1)}\left(T^{(k)}\right)).$$
(67)
By the induction hypothesis,

$$|G^{(k)}|=D_k^{(k)}+|T^{(k)}|.$$
(68)
Recall that, for $`i2`$,

$$D_i^{(k)}=D_{i1}^{(k)}x_i,$$
(69)
and

$$T_{i1}^{(k)}=x_iD_{i1}^{(k)}.$$
(70)
Thus, by Lemma 2.1,

$$x_i=D_i^{(k)}D_{i1}^{(k)}+T_{i1}^{(k)},$$
(71)
for each $`i2`$; summing this over $`i`$ and recalling that $`D_1^{(k)}=x_1`$ yields

$$|x|=D_k^{(k)}+|T^{(k)}|,$$
(72)
so we are done.

We will now show that

$$x(n)=G^{(k)}(n)+F^{(k)}\left(G^{(k)}(l)G^{(k)}(n),ln\right),$$
(73)
for some function $`F^{(k)}`$ to be defined. Again we will prove this by induction on $`k`$, and note that for $`k=2`$, this is given by Lemma 2.1.

A recursive definition of $`F^{(k)}`$ will be implicit in the induction argument. Recall that

$$G^{(k)}=(D_k^{(k)},G^{(k1)}\left(T^{(k)}\right)).$$
(74)
Assuming the induction hypothesis for $`k1`$, we have, for $`i2`$,

$$T_{i1}^{(k)}(n)=G_i^{(k)}(n)+F^{(k1)}\left((G_2^{(k)},\mathrm{},G_k^{(k)})(n,l)\right).$$
(75)
Thus, for $`i2`$, using (71) and the fact that

$$D_i^{(k)}(n)D_{i1}^{(k)}(n)=\underset{ln}{\mathrm{max}}[D_i^{(k)}(n,l)T_{i1}^{(k)}(n,l)],$$

we have

$$x_i(n)=G_i^{(k)}(n)+J_i^{(k)}\left((D_i^{(k)},G_2^{(k)},\mathrm{},G_k^{(k)})(n,l)\right),$$
(76)
where $`J_i^{(k)}`$ is defined on a suitable domain. It is important to note here is that $`J_i^{(k)}`$ does not depend on $`n`$.

In this way, recalling that $`D_k^{(k)}=G_1^{(k)}`$, we obtain

$$x_k(n)=G_k^{(k)}(n)+F_k^{(k)}\left(G^{(k)}(l)G^{(k)}(n),ln\right),$$
(77)
where the function $`F_k^{(k)}`$ is implicitly defined by this identity (on a suitable domain) and does not depend on $`n`$. Observe that we can also recover the sequence of future increments $`x_k(l)x_k(n)`$ as a function, which does not depend on $`n`$, of the sequence $`\{G^{(k)}(l)G^{(k)}(n),ln\}`$.

We can now recover the values $`x_{k1}(n)`$, $`x_{k2}(n)`$, and so on, as follows. By equations (71) with $`i=k`$,

$$D_{k1}^{(k)}(n)=G_1^{(k)}(n)x_k(n)+T_{k1}^{(k)}(n).$$
(78)
It follows that the sequence $`\{D_{k1}^{(k)}(n,l),ln\}`$ is a function, which does not depend on $`n`$, of the sequence $`\{G^{(k)}(l)G^{(k)}(n),ln\}`$. Combining this with (76), we see that

$$x_{k1}(n)=G_{k1}^{(k)}(n)+F_{k1}^{(k)}\left(G^{(k)}(l)G^{(k)}(n),ln\right),$$
(79)
where $`F_{k1}^{(k)}`$ is implicitly defined by this identity (on a suitable domain) and does not depend on $`n`$. Similarly, we can recover the sequence of future increments $`x_k(l)x_k(n)`$ as a function, which does not depend on $`n`$, of the sequence $`\{G^{(k)}(l)G^{(k)}(n),ln\}`$. And so on. Finally, $`x_1(n)`$ is obtained using $`|x|=|G^{(k)}|`$. $`\mathrm{}`$

Proof of Lemma 2.3: We want to show that, for $`(a,b,c)\mathrm{\Lambda }_3`$,

$$a(cb)(bc)=abc,$$
(80)
and for $`(w,x,y)\mathrm{\Lambda }_3`$,

$$w(yx)(xy)=wxy.$$
(81)
First note that these identities are equivalent. To see this, set $`a(n)=nw(n)`$, $`b(n)=nx(n)`$ and $`c(n)=ny(n)`$, then plug these into (80) to obtain (81). We will therefore restrict our attention to the identity (81).

Let $`d=xy`$, $`t=yx`$, $`q=xd`$ and $`u=yd`$. Then (81) becomes

$$w(x+u)(yu)=wxy.$$
(82)
That is, the output of a series of queues in tandem driven by $`(w,x+u,yu)`$ is the same as that of the series driven by $`(w,x,y)`$. Set

$`d_1`$ $`=`$ $`wx`$
$`d_2`$ $`=`$ $`wxy`$
$`\stackrel{~}{d}_1`$ $`=`$ $`w(x+u)`$
$`\stackrel{~}{d}_2`$ $`=`$ $`w(x+u)(yu)`$
and

$`q_1`$ $`=`$ $`wd_1`$
$`q_2`$ $`=`$ $`d_1d_2`$
$`\stackrel{~}{q}_1`$ $`=`$ $`w\stackrel{~}{d}_1`$
$`\stackrel{~}{q}_2`$ $`=`$ $`\stackrel{~}{d}_1\stackrel{~}{d}_2.`$
We want to show that $`d_2=\stackrel{~}{d}_2`$. From the above definitions, this is equivalent to showing that

$$q_1(n)+q_2(n)=\stackrel{~}{q}_1(n)+\stackrel{~}{q}_2(n)$$

for all $`n0`$. We will prove this by induction on $`n`$.

The induction hypothesis $`H`$ is:

$`q_1+q_2=\stackrel{~}{q}_1+\stackrel{~}{q}_2`$, and either

(i) $`\stackrel{~}{q}_2q_20\text{ and }qq_2=0`$, or

(ii) $`\stackrel{~}{q}_2q_2=0\text{ and }qq_20`$.

When $`n=0`$, $`q=q_1=q_2=\stackrel{~}{q}_1=\stackrel{~}{q}_2=0`$, and the induction hypothesis is trivially satisfied. Assume the induction hypothesis holds at time $`n1`$. Note that $`(w,x,yu,u)\mathrm{\Lambda }_4`$, that is, only one of these quantities, if any, can increase by one at time $`n`$. We will consider the following five cases, which are exaustive and mutually exclusive, separately.

* $`(w,x,yu,u)(n)=(w,x,yu,u)(n1)`$
* $`w(n)w(n1)=1`$
* $`x(n)x(n1)=1`$
* $`(yu)(n)(yu)(n1)=1`$
* $`u(n)u(n1)=1`$

Case (a): $`(w,x,yu,u)(n)=(w,x,yu,u)(n1)`$. In this case, nothing changes, and so $`H`$ is preserved.

Case (b): $`w(n)w(n1)=1`$. In this case, $`q_1(n)=q_1(n1)+1`$ and $`\stackrel{~}{q}_1(n)=\stackrel{~}{q}_1(n1)+1`$, the other quantities remain unchanged, and $`H`$ is preserved.

Case (c): $`x(n)x(n1)=1`$. Then $`q(n)=q(n1)+1`$.

Suppose, $`q_1(n1)>\stackrel{~}{q}_1(n1)>0`$. Then $`q_1(n)=q_1(n1)1`$ and $`q_2(n)=q_2(n1)+1`$. Thus, $`qq_2`$ and $`q_1+q_2`$ do not change. Also, $`\stackrel{~}{q}_1(n)=\stackrel{~}{q}_1(n1)1`$ and $`\stackrel{~}{q}_2(n)=\stackrel{~}{q}_2(n1)+1`$. Thus, $`\stackrel{~}{q}_2q_2`$ and $`\stackrel{~}{q}_1+\stackrel{~}{q}_2`$ do not change either, so we still have $`q_1+q_2=\stackrel{~}{q}_1+\stackrel{~}{q}_2`$, and $`H`$ is preserved.

Now suppose $`q_1(n1)>\stackrel{~}{q}_1(n1)=0`$. Note that this implies $`\stackrel{~}{q}_2(n1)q_2(n1)>0`$, so that we are initially in case (i) of the induction hypothesis. In this case, $`q_1(n)=q_1(n1)1`$ and $`q_2(n)=q_2(n1)+1`$, but $`\stackrel{~}{q}_1`$ and $`\stackrel{~}{q}_2`$ do not change. Thus, $`qq_2`$, $`q_1+q_2`$ and $`\stackrel{~}{q}_1+\stackrel{~}{q}_2`$ do not change. The quantity $`\stackrel{~}{q}_2q_2`$ decreases by one, but remains non-negative, so we remain in case (i) and $`H`$ is preserved.

Finally, if $`q_1(n1)=\stackrel{~}{q}_1(n1)=0`$, then we are initially in case (ii) of $`H`$. There is no change to $`q_1,q_2,\stackrel{~}{q}_1`$ or $`\stackrel{~}{q}_2`$, but $`q`$ inceases by one and so we remain in case (ii) and $`H`$ is preserved.

Case (d): $`(yu)(n)(yu)(n1)=1`$. In this case, $`q(n1)>0`$ and $`q`$ decreases by one. The values of $`q_1`$ and $`\stackrel{~}{q}_1`$ do not change.

If we are in case (i) at time $`n1`$, then $`\stackrel{~}{q}_2(n1)q_2(n1)>0`$ and so both $`q_2`$ and $`\stackrel{~}{q}_2`$ also decrease by one; thus, we remain in case (i) and $`H`$ is preserved.

If we are in case (ii) at time $`n1`$, then $`\stackrel{~}{q}_2(n1)=q_2(n1)`$ and either $`q_2`$ and $`\stackrel{~}{q}_2`$ both decrease by one or both remain unchanged. Either way, we remain in case (ii) and $`H`$ is preserved.

Case (e): $`u(n)u(n1)=1`$. Then $`q(n1)=q_2(n1)=0`$ and we are initially in case (i) of $`H`$. The values of $`q,q_1`$ and $`q_2`$ will not change. If $`\stackrel{~}{q}_1>0`$, then $`\stackrel{~}{q}_1`$ decreases by one and $`\stackrel{~}{q}_2`$ increases by one; otherwise, $`\stackrel{~}{q}_1`$ and $`\stackrel{~}{q}_2`$ do not change. Either way, we remain in case (i) and $`H`$ is preserved. $`\mathrm{}`$

Proof of Lemma 2.4: We will prove this by induction on $`k`$. It is certainly true for $`k=2`$, from the definition of $`G^{(2)}`$. Recalling the definition of $`G^{(k)}`$,

$$G^{(k)}=(D_k^{(k)},G^{(k1)}\left(T^{(k)}\right)).$$
(83)
By the induction hypothesis, that the Theorem is true for $`G^{(k1)}`$,

$$G_k^{(k)}=T_{k1}^{(k)}T_{k2}^{(k)}\mathrm{}T_1^{(k)}.$$
(84)
We will now repeatedly apply Lemma 2.3.

$`T_{k1}^{(k)}T_{k2}^{(k)}`$ $`=`$ $`x_kD_{k1}^{(k)}T_{k2}^{(k)}`$
$`=`$ $`x_k(D_{k2}^{(k)}x_{k1})(x_{k1}D_{k2}^{(k)})`$
$`=`$ $`x_kx_{k1}D_{k2}^{(k)}.`$
Similarly,

$`x_kx_{k1}D_{k2}^{(k)}T_{k3}^{(k)}`$ $`=`$ $`x_kx_{k1}(D_{k3}^{(k)}x_{k2})(x_{k2}D_{k3}^{(k)})`$
$`=`$ $`x_kx_{k1}x_{k2}D_{k3}^{(k)},`$
and so on. $`\mathrm{}`$


format: text

text:
# On Povzner–Wienholtz-type Self-Adjointness Results for Matrix-Valued Sturm–Liouville Operators

## 1. Introduction

In two recent papers concerned with certain aspects of inverse spectral theory for matrix-valued one dimensional Schrödinger operators (cf. , ), it became necessary to infer the limit point case at $`\pm \mathrm{}`$ from nonoscillatory properties of the Schrödinger differential expression at $`\pm \mathrm{}`$. Put differently, it was necessary to conclude that boundedness from below implies (essential) self-adjointness for matrix-valued Schrödinger operators under minimal regularity assumptions on the potential coefficient. While the problem of self-adjointness of matrix-valued (and more generally, operator-valued) differential operators has been studied in the literature (see, e.g.,  and ), apparently, no result assuming lower semiboundedness of the associated minimal differential operator alone, appears to be known. (Reference , e.g., assumes additional local boundedness of the operator-valued potential in the Schrödinger operator in question.) In this note we close this gap by proving Povzner–Wienholtz-type self-adjointness results for one-dimensional scalar and matrix-valued Sturm–Liouville operators under optimal conditions on the potential coefficient.

Hartman  and Rellich  were first to show that boundedness below of the scalar Sturm–Liouville expression $`\mathrm{}=r^1(\frac{d}{dx}p\frac{d}{dx}+q)`$ and integral conditions on the functions $`r`$ and $`p`$, which are necessarily satisfied when $`p,r=1`$, are together sufficient to imply essential self-adjointness of the minimal operator for $`\mathrm{}`$ (cf. Section 2). Independently, Povzner  and subsequently Wienholtz  were first to show that semi-boundedness for the operator $`L_0=(\mathrm{\Delta }+q)C_0^{\mathrm{}}(^n)`$ implies its essential self-adjointness when $`q`$ is real-valued and continuous. This result has since been shown for more general $`q`$ as may be seen by the work and references found in , , , and . Closely related self-adjointness results based on the concept of a finite rate of propagation were discussed by Berezanskii \[2, Sect. VI.1.7\] and further devloped, for instance, in , \[4, Sect. 13.8\], , . These works typically address the scalar case for ordinary or partial differential expressions, and not the one-dimensional matrix setting that is our interest. After completing our work we became aware of a recent very detailed study of essential self-adjointness of general Schrödinger operators of the type $`D^{}D+V`$, where $`D`$ is a first-order elliptic differential operator acting on the space of sections of a hermitian vector bundle over a manifold, by Braverman, Milatovic, and Shubin . This paper appears to contain the state of the art in the multi-dimensional context.

In Section 2, we define Sturm–Liouville operators for the scalar case on the whole or half-line and recall in Theorem 2.3 the equivalence between the boundedness below of our operators and the nonoscillation of solutions of the associated homogeneous equation near endpoints of the given interval. The fundamental results of Hartman  and of Rellich  are recalled in Theorem 2.4 for the scalar Sturm–Liouville case. In Section 3, we obtain in Theorem 3.1 a result for the scalar Sturm–Liouville operator, and in Theorem 3.7 a result for the matrix-valued Sturm–Liouville operator, like that of Hartman and Rellich but independent of both as seen in Examples 3.3 and 3.4.

Hartman proved his result using the concept of principal and nonprincipal solutions while Rellich obtained a proof of this result by focusing upon the boundedness below of the associated minimal operator. Each of these approaches appears not to extend to the matrix setting. Instead, our results are obtained using the approach introduced by Wienholtz  to prove the result first due to Povzner .

## 2. Self-adjointness for the scalar Sturm–Liouville case

Beginning with the scalar case, we introduce the following basic assumptions.

###### Hypothesis 2.1.

$`(i)`$ Let $`c<b\mathrm{}`$ and suppose that $`p,q,r`$ are $`(`$Lebesgue$`)`$ measurable on $`[c,b)`$, and that

$`p>0,r>0\text{ a.e. on }[c,b)\text{}q\text{ real-valued},`$ (2.1a)
$`1/p,q,rL^1([c,d];dx)\text{ for all }d[c,b).`$ (2.1b)
$`(ii)`$ Let $`\mathrm{}a<b\mathrm{}`$ and suppose that $`p,q,r`$ are $`(`$Lebesgue$`)`$ measurable on $`(a,b)`$, and that

$`p>0,r>0\text{ a.e. on }(a,b)\text{}q\text{ real-valued},`$ (2.2a)
$`1/p,q,rL_{\text{loc}}^1((a,b);dx).`$ (2.2b)
The case $`\mathrm{}a<c`$ and $`p,q,r`$ (Lebesgue) measurable on $`(a,c]`$, $`p>0,r>0`$ a.e. on $`(a,c]`$, $`q`$ real-valued, and $`1/p,q,rL^1([d,c];dx)`$, for all $`d(a,c]`$, follows upon reflection from case $`(i)`$ in Hypothesis 2.1 and hence will not be separately discussed in the following.

Given Hypothesis 2.1, we consider the differential expression

$$\mathrm{}=\frac{1}{r}\left(\frac{d}{dx}p\frac{d}{dx}+q\right)$$
(2.3)
on $`[c,b)`$ and $`(a,b)`$, respectively. Next, we introduce for $`c(a,b)`$,

$`𝒟_{\mathrm{max},\text{c,b}}`$ $`=\{uL^2([c,b);rdx)|u,pu^{}AC([c,d])\text{ for all }d[c,b)\text{;}`$
$`u(c)=0;\mathrm{}uL^2([c,b);rdx)\},`$ (2.4)
$`𝒟_{\mathrm{min},\text{c,b}}`$ $`=\{u𝒟_{\mathrm{max},\text{c,b}}|\text{supp}(u)[c,b)\text{ compact}\},`$ (2.5)
$`𝒟_{\mathrm{max}}`$ $`=\{uL^2((a,b);rdx)|u,pu^{}AC_{\text{loc}}((a,b));`$ (2.6)
$`\mathrm{}uL^2((a,b);rdx)\},`$ (2.7)
$`𝒟_{\mathrm{min}}`$ $`=\{u𝒟_{\mathrm{max}}|\text{supp}(u)(a,b)\text{ compact}\},`$ (2.8)
where $`AC_{\text{loc}}((a,b))`$ denotes the set of locally absolutely continuous functions on $`(a,b)`$ and $`AC([c,d])`$ represents the set of absolutely continuous functions on $`[c,d]`$.

Minimal operators $`T_{\mathrm{min},\text{c,b}}`$ and $`T_{\mathrm{min}}`$ and maximal operators $`T_{\mathrm{max},\text{c,b}}`$ and $`T_{\mathrm{max}}`$ in $`L^2((c,b);rdx)`$ and $`L^2((a,b);rdx)`$, respectively, associated with $`\mathrm{}`$, are then defined by

$`T_{\mathrm{min},\text{c,b}}u`$ $`=\mathrm{}u,u\text{dom}(T_{\mathrm{min},\text{c,b}})=𝒟_{\mathrm{min},\text{c,b}},`$ (2.9)
$`T_{\mathrm{max},\text{c,b}}u`$ $`=\mathrm{}u,u\text{dom}(T_{\mathrm{max},\text{c,b}})=𝒟_{\mathrm{max},\text{c,b}},`$ (2.10)
$`T_{\mathrm{min}}u`$ $`=\mathrm{}u,u\text{dom}(T_{\mathrm{min}})=𝒟_{\mathrm{min}},`$ (2.11)
$`T_{\mathrm{max}}u`$ $`=\mathrm{}u,u\text{dom}(T_{\mathrm{max}})=𝒟_{\mathrm{max}},`$ (2.12)
respectively. Then $`T_{\mathrm{min}}`$ and $`T_{\mathrm{min},\text{c,b}}`$ are densely defined and (cf. \[16, p. 64, 88\])

$`T_{\mathrm{min},\text{c,b}}^{}{}_{}{}^{}`$ $`=T_{\mathrm{max},\text{c,b}},`$ (2.13)
$`T_{\mathrm{min}}^{}{}_{}{}^{}`$ $`=T_{\mathrm{max}}.`$ (2.14)
In the following we will frequently refer to solutions $`u(,z)`$ of $`\mathrm{}u=zu`$ for some $`z`$. Such solutions are always assumed to be distributional solutions, that is, we tacitly assume

$$u(,z),pu^{}(,z)AC([c,d]),d[c,b)\text{ (resp., }AC_{\text{loc}}((a,b))\text{, etc.)}$$
(2.15)
in such a case.

Next we recall the standard notion of (non)oscillatory differential expressions.

###### Definition 2.2.

Assume Hypothesis 2.1$`(ii)`$ and fix $`c(a,b)`$. Then $`\mathrm{}`$ is said to be nonoscillatory near $`a`$ $`(`$or $`b`$$`)`$ for some $`\lambda `$ if and only if every real-valued solution $`u`$ of $`\mathrm{}u=\lambda u`$ has finitely many zeros in $`(a,c)`$ (resp., $`(c,b)`$). Otherwise, $`\mathrm{}`$ is called oscillatory near $`a`$ $`(`$resp., $`b`$$`)`$.

The following is a key result in this connection.

###### Theorem 2.3 (, , , , ).

Assume Hypothesis 2.1$`(i)`$. Then the following assertions are equivalent:
$`(i)`$ $`T_{\mathrm{min},\text{c,b}}`$ $`(`$and hence any symmetric extension of $`T_{\mathrm{min},\text{c,b}}`$$`)`$ is bounded from below.
$`(ii)`$ There exists a $`\lambda _0`$ such that $`\mathrm{}`$ is nonoscillatory near $`b`$ for all $`\lambda <\lambda _0`$.
Assume Hypothesis 2.1$`(ii)`$. Then the following assertions are equivalent:
$`(iii)`$ $`T_{\mathrm{min}}`$ $`(`$and hence any symmetric extension of $`T_{\mathrm{min}}`$$`)`$ is bounded from below.
$`(iv)`$ There exists a $`\lambda _0`$ such that $`\mathrm{}`$ is nonoscillatory near $`a`$ and $`b`$ for all $`\lambda <\lambda _0`$.

Next, we mention a fundamental result which links the nonoscillatory behavior at one end point with the limit point property at that endpoint.

###### Theorem 2.4 (Hartman  (cf. also , )).

Suppose Hypothesis 2.1$`(i)`$ and assume that for some $`\lambda _0`$, $`\mathrm{}\lambda _0`$ is nonoscillatory near $`b`$, or equivalently, that $`T_{\mathrm{min},\text{c,b}}`$ is bounded from below. Then, if

$$\left|^b𝑑x\left(\frac{r(x)}{p(x)}\right)^{1/2}\right|=\mathrm{},$$
(2.16)
$`\mathrm{}`$ is in the limit point case at $`b`$.

Originally, Hartman proved the special case $`r=1`$ by an elegant application of the concept of (non)principal solutions $`(`$the proof easily extends to the general situation $`r1`$ described in Theorem 2.4$`)`$. Theorem 2.4 was subsequently derived by Rellich  by focusing on operators $`T_{\mathrm{min},\text{c,b}}`$ bounded from below. (Actually, Hartman and Rellich assume $`p,p^{}C((a,b))`$ and $`q,r`$ piecewise continuous in $`(a,b)`$ in addition to Hypothesis 2.1 (i) but this is easily seen to be unnecessary.)

For an extension of Theorem 2.4 to polynomials of $`\mathrm{}`$ we refer to Read .

For essential self-adjointness results using conditions of the type (2.16) but with semiboundedness from below of the corresponding minimal differential operators replaced by alternative conditions, we refer to the recent work by Lesch and Malamud . The latter treats the case of matrix-valued Schrödinger operators as well as the case of general canonical systems.

Finally, for extensions of Theorem 2.4 to the multi-dimensional case we refer to our account in the introduction.

## 3. Povzner–Wienholtz-type self-adjointness results

Next we formulate a result that resembles one by Povzner  in the context of partial differential operators. We will adapt a method of proof due to Wienholtz , who independently proved Povzner’s result. (Wienholtz’s proof is also reproduced in Glazman \[8, Chapter1, Theorem 35\].)

###### Theorem 3.1.

Assume Hypothesis 2.1$`(i)`$ with $`b=\mathrm{}`$ and $`pAC([c,c+\rho ])`$ for all $`\rho >0`$ and $`r^1(p^{})^2,r^1L_{\text{loc}}^1((c,\mathrm{}))`$. Moreover, suppose that $`T_{\mathrm{min},\text{c},\mathrm{}}`$ is bounded from below. Then, if

$$p/r_{L^{\mathrm{}}((\rho /2,\rho ))}\underset{\rho \mathrm{}}{=}O(\rho ^2),$$
(3.1)
$`\mathrm{}`$ is in the limit point case at $`\mathrm{}`$.

###### Proof.

By von Neumann’s theory of self-adjoint extensions (cf. \[20, p. 137\]), to prove that $`\mathrm{}`$ is in the limit point case at $`\mathrm{}`$, or equivalently, that $`T_{\mathrm{min},\text{c},\mathrm{}}`$ is essentially self-adjoint and hence its closure $`T_{\mathrm{max},\text{c},\mathrm{}}`$ is self-adjoint (since $`\overline{T_{\mathrm{min},\text{c},\mathrm{}}}=T_{\mathrm{min},\text{c},\mathrm{}}^{}=T_{\mathrm{max},\text{c},\mathrm{}}`$), we need to show that

$$\mathrm{ker}(T_{\mathrm{min},\text{c},\mathrm{}}^{}C)=\{0\}$$
(3.2)
for $`C>0`$ sufficiently large. Next, we assume, without loss of generality, that for $`u\text{dom}(T_{\mathrm{min},\text{c},\mathrm{}})`$

$$_c^{\mathrm{}}r(x)𝑑x\overline{u(x)}(\mathrm{}u)(x)>_c^{\mathrm{}}r(x)𝑑x|u(x)|^2,$$
(3.3)
so we may take $`C=0`$ in (3.2). In addition, we choose $`c=0`$ for simplicity.

To start the proof we assume that $`\mathrm{}`$ is not in the limit point case at $`\mathrm{}`$. Then, by Weyl’s alternative, all solutions $`u`$ of

$$\mathrm{}u=0$$
(3.4)
are necessarily in $`L^2([0,\mathrm{});rdx)`$, and hence there exists a nontrivial real-valued solution $`\widehat{u}L^2([0,\mathrm{});rdx)`$ of (3.4) that satisfies the Dirichlet boundary condition $`\widehat{u}(0)=0`$. To complete the proof, it is sufficient to show that (3.3) rules out the existence of such a solution $`\widehat{u}L^2([0,\mathrm{});rdx)`$ of (3.4).

Let

$$u_\rho (x)=\theta _\rho (x)\widehat{u}(x),0x<\mathrm{},$$
(3.5)
where

$$\theta _\rho (x)=\theta (x/\rho ),\theta ^{\mathrm{}}([0,\mathrm{})),\theta (x)=\{\begin{array}{cc}1\hfill & 0x1/2,\hfill \\ 0\hfill & x>1.\hfill \end{array}$$
(3.6)
As defined, $`u_\rho \text{dom}(T_{\mathrm{min},0,\mathrm{}})`$. Indeed, since $`pAC([0,\rho ])`$ for all $`\rho >0`$ by hypothesis, one verifies that

$`\mathrm{}u_\rho `$ $`=\mathrm{}(\theta _\rho \widehat{u})=\theta _\rho (\mathrm{}\widehat{u})r^1(p\theta _\rho ^{})^{}\widehat{u}2r^1\theta _\rho ^{}(p\widehat{u}^{})`$
$`=r^1p^{}\theta _\rho ^{}\widehat{u}r^1p\theta _\rho ^{\prime \prime }\widehat{u}2r^1\theta _\rho ^{}(p\widehat{u}^{}).`$ (3.7)
Since

$`{\displaystyle _{\rho /2}^\rho }𝑑xr^1(p^{})^2(\theta _\rho ^{})^2\widehat{u}^2(\theta _\rho ^{})^2\widehat{u}^2_{L^{\mathrm{}}((\rho /2,\rho ))}{\displaystyle _{\rho /2}^\rho }𝑑xr^1(p^{})^2<\mathrm{},`$ (3.8)
$`{\displaystyle _{\rho /2}^\rho }𝑑x(r^1p)\left[p(\theta _\rho ^{\prime \prime })^2\widehat{u}^2\right](\rho /2)p/r_{L^{\mathrm{}}((\rho /2,\rho ))}p_{L^{\mathrm{}}((\rho /2,\rho ))}`$
$`\times (\theta _\rho ^{\prime \prime })^2\widehat{u}^2_{L^{\mathrm{}}((\rho /2,\rho ))}<\mathrm{},`$ (3.9)
and
$`{\displaystyle _{\rho /2}^\rho }𝑑xr^1(\theta _\rho ^{})^2(p\widehat{u}^{})^2(\theta _\rho ^{})^2_{L^{\mathrm{}}((\rho /2,\rho ))}(p\widehat{u}^{})^2_{L^{\mathrm{}}((\rho /2,\rho ))}`$
$`\times {\displaystyle _{\rho /2}^\rho }dxr^1<\mathrm{},`$ (3.10)
one obtains $`u_\rho \text{dom}(T_{\mathrm{min},0,\mathrm{}})`$. Hence $`u_\rho `$ satisfies (3.3), that is,

$$_0^{\mathrm{}}r(x)𝑑x\theta _\rho (x)^2\widehat{u}(x)^2<_0^{\mathrm{}}r(x)𝑑xu_\rho (x)(\mathrm{}u_\rho )(x).$$
(3.11)
Since

$$ru_\rho (\mathrm{}u_\rho )=\theta _\rho (p\theta _\rho ^{})^{}\widehat{u}^22\theta _\rho \theta _\rho ^{}\widehat{u}(p\widehat{u}^{})=(\theta _\rho ^{})^2p\widehat{u}^2\left[\theta _\rho \theta _\rho ^{}p\widehat{u}^2\right]^{}$$
(3.12)
and $`\theta _\rho (\rho )=\theta _\rho ^{}(0)=0`$, one obtains

$`{\displaystyle _0^{\rho /2}}r(x)𝑑x\widehat{u}(x)^2<{\displaystyle _0^{\mathrm{}}}r(x)𝑑x\theta _\rho (x)^2\widehat{u}(x)^2`$
$`<{\displaystyle _0^{\mathrm{}}}r(x)𝑑xu_\rho (x)(\mathrm{}u_\rho )(x)={\displaystyle _0^{\mathrm{}}}𝑑x\theta _\rho ^{}(x)^2p(x)\widehat{u}(x)^2`$
$`={\displaystyle _0^{\mathrm{}}}r(x)𝑑x\theta _\rho ^{}(x)^2[p(x)/r(x)]\widehat{u}(x)^2`$
$`{\displaystyle \frac{C^2}{\rho ^2}}p/r_{L^{\mathrm{}}((\rho /2,\rho ))}{\displaystyle _{\rho /2}^\rho }r(x)𝑑x\widehat{u}(x)^2`$
$`\underset{\rho \mathrm{}}{=}O(1){\displaystyle _{\rho /2}^\rho }r(x)𝑑x\widehat{u}(x)^2\underset{\rho \mathrm{}}{=}o(1)`$ (3.13)
for some constant $`C>0`$, implying $`\widehat{u}=0`$ a.e. on $`[0,\mathrm{})`$. ∎

###### Remark 3.2.

Even though Theorems 2.4 (for $`b=\mathrm{}`$) and 3.1 show some resemblance, their proofs follow quite different strategies. In particular, the proof of Theorem 3.1 seems to work only for half-lines (i.e., $`b=\mathrm{}`$). Moreover, as the following examples show, neither theorem implies the other.

###### Example 3.3.

Consider $`c=0`$, $`b=\mathrm{}`$, $`q=0`$, $`p,rC^{\mathrm{}}([0,\mathrm{}))`$, and

$$\frac{r(x)}{p(x)}=\frac{1}{x^2\text{ln}(x)}\text{ for }xe.$$
(3.14)
Then one easily verifies that condition (2.16) is satisfied while (3.1) is not.

###### Example 3.4.

Consider $`c=0`$, $`b=\mathrm{}`$ $`q=0`$, $`p,rC([0,\mathrm{}))`$, and

$$\frac{r(x)}{p(x)}=\{\begin{array}{cc}\frac{1}{x^2},\hfill & x[n,n+(1/n)],n,\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}$$
(3.15)
Then one easily verifies that condition (3.1) is satisfied while (2.16) is not.

We note that $`q=0`$ implies the nonoscillatory behavior of $`\mathrm{}`$ since solving $`\mathrm{}u=0`$ readily yields

$$u(x)=C^x𝑑x^{}p(x^{})^1+D,C,D,$$
(3.16)
and clearly $`u`$ in (3.16) has at most one zero. Moreover, if $`r`$ is not integrable at $`\mathrm{}`$, there exists a particular solution $`u_0=DL^2([0,\mathrm{});rdx)`$ (choosing $`D0`$ in (3.16)) of $`\mathrm{}u=0`$ and hence $`\mathrm{}`$ is also in the limit point case in this situation.

###### Remark 3.5.

Examining the proof of Theorem 3.1, it is possible to relax the assumption $`pAC_{\text{loc}}()`$ by an appropriate modification of condition (3.1). In fact, modifying the cutoff function $`\theta _\rho `$ in (3.6) as follows,

$`\theta _\rho C^{\mathrm{}}([0,\mathrm{})),\theta _\rho (x)=\{\begin{array}{cc}1,\hfill & 0x\rho /2,\hfill \\ f_\rho \left(\rho ^1_0^x𝑑x^{}p(x^{})^1\right),\hfill & \rho /2x\rho ,\hfill \\ 0,\hfill & x\rho ,\hfill \end{array}`$ (3.17)
$`f_\rho \left(\rho ^1\underset{0}{\overset{\rho /2}{}}𝑑xp(x)^1\right)=1,f_\rho \left(\rho ^1\underset{0}{\overset{\rho }{}}𝑑xp(x)^1\right)=0`$ (3.18)
for an appropriate smooth function $`f_\rho `$, and assuming

$$(pr)^1\left[f_\rho ^{}\left(\rho ^1\underset{0}{\overset{}{}}𝑑x^{}p(x^{})^1\right)\right]^2_{L^{\mathrm{}}((\rho /2,\rho ))}\underset{\rho \mathrm{}}{=}O(\rho ^2),$$
(3.19)
instead of condition (3.1), one verifies that

$`\mathrm{}u_\rho `$ $`=\mathrm{}(\theta _\rho \widehat{u})=\theta _\rho (\mathrm{}\widehat{u})r^1(p\theta _\rho ^{})^{}\widehat{u}2r^1\theta _\rho ^{}(p\widehat{u}^{})`$
$`=r^1(p\theta _\rho ^{})^{}\widehat{u}2r^1\theta _\rho ^{}(p\widehat{u}^{})`$
$`=\rho ^2(pr)^1f_\rho ^{\prime \prime }\left(\rho ^1\underset{0}{\overset{x}{}}𝑑x^{}p(x^{})^1\right)\widehat{u}`$
$`2\rho ^1(pr)^1f_\rho ^{}\left(\rho ^1\underset{0}{\overset{x}{}}𝑑x^{}p(x^{})^1\right)(p\widehat{u}^{})`$ (3.20)
is well-defined. Following the proof of Theorem 3.1 step by step then results in

$`{\displaystyle _0^{\mathrm{}}}𝑑x\theta _\rho ^{}(x)^2p(x)\widehat{u}(x)^2={\displaystyle _0^{\mathrm{}}}r(x)𝑑x\theta _\rho ^{}(x)^2p(x)r(x)^1\widehat{u}(x)^2`$
$`{\displaystyle \frac{C^2}{\rho ^2}}(pr)^1\left[f_\rho ^{}\left(\rho ^1\underset{0}{\overset{}{}}𝑑x^{}p(x^{})^1\right)\right]^2_{L^{\mathrm{}}((\rho /2,\rho ))}{\displaystyle _{\rho /2}^\rho }r(x)𝑑x\widehat{u}(x)^2`$ (3.21)
for some constant $`C>0`$ and hence again in $`\widehat{u}=0`$ a.e. on $`[0,\mathrm{})`$ as in (3.13).

When trying to extend Theorem 2.4 to the matrix-valued context, one observes that the use of (matrix-valued) principal solutions can indeed exclude the limit circle case at $`b`$ under the assumption of $`T_{\mathrm{min},\text{c,b}}`$ being bounded from below. However, it is not clear how to exclude all intermediate cases between those of limit circle and limit point that we may then infer the limit point case at $`b`$. The strategy of proof of Theorem 3.1, on the other hand, will now be shown to extend to the matrix-valued case in due course.

Throughout the rest of this note all matrices will be considered over the field of complex numbers $``$, and the corresponding linear space of $`k\times \mathrm{}`$ matrices will be denoted by $`^{k\times \mathrm{}}`$, $`k,\mathrm{}`$. Moreover, $`I_k`$ denotes the identity matrix in $`^{k\times k}`$ and $`M^{}`$ the adjoint (i.e., complex conjugate transpose) of a matrix $`M`$. A positive definite matrix $`P`$ is denoted by $`P>0`$, a nonnegative matrix $`Q`$ by $`Q0`$.

We start by introducing the following hypothesis.

###### Hypothesis 3.6.

Let $`c<b\mathrm{}`$ and suppose that $`P,Q,R^{m\times m}`$ are $`(`$Lebesgue$`)`$ measurable on $`[c,b)`$, and that

$`P>0,R>0\text{ a.e. on }[c,b)\text{}Q=Q^{}\text{ self-adjoint},`$ (3.22a)
$`P^1,Q,RL^1([c,d];dx)^{m\times m}\text{ for all }d[c,b).`$ (3.22b)
As in the scalar context, the analogous case of the half-line $`(a,c]`$ follows upon reflection from the case $`[c,b)`$ in Hypothesis 3.6 and hence is not separately discussed in the following.

Given Hypothesis 3.6, we consider the $`m\times m`$ matrix-valued differential expression

$$L=R^1\left(\frac{d}{dx}P\frac{d}{dx}+Q\right)$$
(3.23)
on $`[c,b)`$. Next, we introduce

$`𝒟_{\mathrm{max},\text{c,b}}`$ $`=\{uL^2([c,b);Rdx)^m|u,Pu^{}AC([c,d])^m\text{ for all }d[c,b)\text{;}`$
$`u(c)=0;\mathrm{}uL^2([c,b);Rdx)^m\},`$ (3.24)
$`𝒟_{\mathrm{min},\text{c,b}}`$ $`=\{u𝒟_{\mathrm{max},\text{c,b}}|\text{supp}(u)[c,b)\text{ compact}\},`$ (3.25)
where $`AC([c,d])^m`$ denotes the set of absolutely continuous vectors in $`^m`$ on $`[c,d]`$. Moreover, $`L^2(\mathrm{\Omega };Rdx)^m`$ denotes the Hilbert space of $`^m`$-valued (Lebesgue) measurable vectors $`u,v`$ on $`\mathrm{\Omega }`$ corresponding to the $`m\times m`$ matrix-valued measure $`Rdx`$ with scalar product $`(u,v)_{L^2(\mathrm{\Omega };Rdx)^m}`$, given by

$$(u,v)_{L^2(\mathrm{\Omega };Rdx)^m}=_\mathrm{\Omega }𝑑x(u(x),R(x)v(x))_^m,$$
(3.26)
where $`(f,g)_^m=_{k=1}^m\overline{f}_kg_k,f,g^m`$. For notational simplicity we will abbreviate the scalar product in $`L^2(\mathrm{\Omega };Rdx)^m`$ by $`(u,v)`$ only.

Minimal operators $`T_{\mathrm{min},\text{c,b}}`$ and maximal operators $`T_{\mathrm{max},\text{c,b}}`$ in $`L^2((c,b);Rdx)^m`$ associated with $`L`$ are then defined as in the scalar context by

$`T_{\mathrm{min},\text{c,b}}u`$ $`=Lu,u\text{dom}(T_{\mathrm{min},\text{c,b}})=𝒟_{\mathrm{min},\text{c,b}},`$ (3.27)
$`T_{\mathrm{max},\text{c,b}}u`$ $`=Lu,u\text{dom}(T_{\mathrm{max},\text{c,b}})=𝒟_{\mathrm{max},\text{c,b}},`$ (3.28)
respectively. Then $`T_{\mathrm{min}}`$ and $`T_{\mathrm{min},\text{c,b}}`$ are densely defined and (2.13)–(2.14) continue to hold in the matrix-valued context.

After these preparations we are ready for the matrix-valued extension of Theorem 3.1, the principal objective of this note. (We denote by $`M`$ the operator norm of an $`m\times m`$ matrix $`M`$.)

###### Theorem 3.7.

Assume Hypothesis 3.6 with $`b=\mathrm{}`$ and $`PAC([c,c+\rho ])^{m\times m}`$ for all $`\rho >0`$ and $`P^{}R^1P^{},R^1L_{\text{loc}}^1((c,\mathrm{}))`$. Moreover, suppose that $`T_{\mathrm{min},\text{c},\mathrm{}}`$ is bounded from below. Then, if

$$\text{ess\hspace{0.17em}sup}_{x[\rho /2,\rho ]}R(x)^{1/2}P(x)R(x)^{1/2}\underset{\rho \mathrm{}}{=}O(\rho ^2),$$
(3.29)
$`L`$ is in the limit point case at $`\mathrm{}`$.

###### Proof.

The strategy of proof is completely analogous to the scalar context, Theorem 3.1. As before we need to show that

$$\mathrm{ker}(T_{\mathrm{min},\text{c},\mathrm{}}^{}C)=\{0\}$$
(3.30)
for $`C>0`$ sufficiently large. Again we assume, without loss of generality, that for $`u\text{dom}(T_{\mathrm{min},\text{c},\mathrm{}})`$

$$_c^{\mathrm{}}𝑑x(u(x),R(x)(Lu)(x))_^m>_c^{\mathrm{}}𝑑x(u(x),R(x)u(x))_^m,$$
(3.31)
so we may take $`C=0`$ in (3.30). Moreover, we choose $`c=0`$ as before.

To start the proof we assume that $`L`$ is not in the limit point case at $`\mathrm{}`$. Then, by the matrix analog of Weyl’s alternative (cf., e.g., , ), $`m+1`$ solutions $`u`$ of

$$Lu=0$$
(3.32)
are necessarily in $`L^2([0,\mathrm{});Rdx)^m`$, and hence there exists a nontrivial real-valued solution $`\widehat{u}L^2([0,\mathrm{});Rdx)`$ of (3.4) that satisfies the Dirichlet boundary condition $`\widehat{u}(0)=0`$. To complete the proof, it is sufficient to show that (3.31) rules out the existence of such a solution $`\widehat{u}`$.

Let

$$u_\rho (x)=\theta _\rho (x)\widehat{u}(x),0x<\mathrm{},$$
(3.33)
where

$$\theta _\rho (x)=\theta (x/\rho ),\theta ^{\mathrm{}}([0,\mathrm{})),\theta (x)=\{\begin{array}{cc}1\hfill & 0x1/2,\hfill \\ 0\hfill & x>1.\hfill \end{array}$$
(3.34)
As defined, $`u_\rho \text{dom}(T_{\mathrm{min},0,\mathrm{}})`$. Indeed, since $`PAC([0,\rho ])`$ for all $`\rho >0`$ by hypothesis, one verifies that

$`Lu_\rho `$ $`=L(\theta _\rho \widehat{u})=\theta _\rho (L\widehat{u})R^1(P\theta _\rho ^{})^{}\widehat{u}2R^1\theta _\rho ^{}(P\widehat{u}^{})`$
$`=R^1P^{}\theta _\rho ^{}\widehat{u}R^1P\theta _\rho ^{\prime \prime }\widehat{u}2R^1\theta _\rho ^{}(P\widehat{u}^{}).`$ (3.35)
Since

$`{\displaystyle _{\rho /2}^\rho }𝑑x(\theta _\rho ^{}\widehat{u},P^{}R^1P^{}\theta _\rho ^{}\widehat{u})_^m\text{ess\hspace{0.17em}sup}_{x[\rho /2,\rho ]}\theta _\rho ^{}(x)\widehat{u}(x)_^m^2`$
$`\times {\displaystyle _{\rho /2}^\rho }dxP^{}R^1P^{}<\mathrm{},`$ (3.36)
$`{\displaystyle _{\rho /2}^\rho }𝑑x(P\theta _\rho ^{\prime \prime }\widehat{u},R^1P\theta _\rho ^{\prime \prime }\widehat{u})_^m={\displaystyle _{\rho /2}^\rho }𝑑x(P^{1/2}\theta _\rho ^{\prime \prime }\widehat{u},P^{1/2}R^1P^{1/2}P^{1/2}\theta _\rho ^{\prime \prime }\widehat{u})_^m`$
$`(\rho /2)\text{ess\hspace{0.17em}sup}_{x[\rho /2,\rho ]}P(x)^{1/2}^2\text{ess\hspace{0.17em}sup}_{x[\rho /2,\rho ]}\theta _\rho ^{\prime \prime }(x)\widehat{u}(x)_^m^2`$
$`\times \text{ess\hspace{0.17em}sup}_{x[\rho /2,\rho ]}P(x)^{1/2}R(x)^1P(x)^{1/2}`$
$`=(\rho /2)\text{ess\hspace{0.17em}sup}_{x[\rho /2,\rho ]}P(x)^{1/2}^2\text{ess\hspace{0.17em}sup}_{x[\rho /2,\rho ]}\theta _\rho ^{\prime \prime }(x)\widehat{u}(x)_^m^2`$
$`\times \text{ess\hspace{0.17em}sup}_{x[(\rho /2,\rho )]}R(x)^{1/2}P(x)R(x)^{1/2}<\mathrm{},`$ (3.37)
and
$`{\displaystyle _{\rho /2}^\rho }(R^1\theta _\rho ^{}(P\widehat{u}^{}),RR^1\theta _\rho ^{}(P\widehat{u}^{}))_^m`$
$`(\theta _\rho ^{})^2_{L^{\mathrm{}}([\rho /2,\rho ])}\text{ess\hspace{0.17em}sup}_{x[\rho /2,\rho ]}P(x)\widehat{u}^{}(x)_^m^2{\displaystyle _{\rho /2}^\rho }𝑑xR^1<\mathrm{},`$ (3.38)
and thus $`u_\rho \text{dom}(T_{\mathrm{min},0,\mathrm{}})`$. Hence $`u_\rho `$ satisfies (3.31), that is,

$$_0^{\mathrm{}}𝑑x\theta _\rho (x)^2(\widehat{u}(x),R(x)\widehat{u}(x))_^m<_0^{\mathrm{}}𝑑x(u_\rho (x),R(x)(Lu_\rho )(x))_^m.$$
(3.39)
Since

$`\left[(u\rho ,R(Lu_\rho ))_^m+(R(Lu_\rho ),u_\rho )_^m\right]/2=\left(\theta _\rho ^{}\right)^2(\widehat{u},P\widehat{u})_^m\left[\theta _\rho \theta _\rho ^{}(\widehat{u},P\widehat{u})_^m\right]^{}`$ (3.40)
and $`\theta _\rho (\rho )=\theta _\rho ^{}(0)=0`$, one obtains

$`{\displaystyle _0^{\rho /2}}𝑑x(\widehat{u}(x),R(x)\widehat{u}(x))_^m<{\displaystyle _0^{\mathrm{}}}𝑑x\theta _\rho (x)^2(\widehat{u}(x),R(x)\widehat{u}(x))_^m`$
$`<{\displaystyle _0^{\mathrm{}}}(u_\rho (x),R(x)(Lu_\rho )(x))_^m`$
$`=(1/2){\displaystyle _0^{\mathrm{}}}(u_\rho (x),R(x)(Lu_\rho )(x))_^m+(1/2){\displaystyle _0^{\mathrm{}}}(R(x)(Lu_\rho )(x),u_\rho (x))_^m`$
$`={\displaystyle _0^{\mathrm{}}}\theta _\rho ^{}(x)^2(\widehat{u}(x),P(x)\widehat{u}(x))_^m`$
$`={\displaystyle _0^{\mathrm{}}}𝑑x\theta _\rho ^{}(x)^2(R(x)^{1/2}\widehat{u}(x),R(x)^{1/2}P(x)R(x)^{1/2}R(x)^{1/2}\widehat{u}(x))_^m`$
$`{\displaystyle \frac{C^2}{\rho ^2}}\text{ess\hspace{0.17em}sup}_{x[\rho /2,\rho ]}R(x)^{1/2}P(x)R(x)^{1/2}{\displaystyle _{\rho /2}^\rho }𝑑x(\widehat{u}(x),R(x)\widehat{u}(x))_^m`$
$`\underset{\rho \mathrm{}}{=}O(1){\displaystyle _{\rho /2}^\rho }𝑑x(\widehat{u}(x),R(x)\widehat{u}(x))_^m\underset{\rho \mathrm{}}{=}o(1)`$ (3.41)
for some constant $`C>0`$, implying $`\widehat{u}=0`$ a.e. on $`[0,\mathrm{})`$. ∎

Acknowledgements. We are indebted to Mark Malamud and Fedor Rofe-Beketov for useful comments and hints to the literature. We also thank the referee for a very careful reading of our manuscript and for pointing out a number of improvements concerning the presentation of our results.