\documentclass[ALCO,Unicode,published]{cedram}
\usepackage{amsmath,amsxtra,amsthm,amssymb,graphics,hyperref,graphicx}
\usepackage{latexsym,color}
\newcommand{\ncom}{\newcommand}
\newcommand{\cA}{{\mathcal M}}
\newcommand{\cB}{{\mathcal B}}
\newcommand{\cD}{{\mathcal Z}}
\newcommand{\cE}{{\mathcal E}}
\newcommand{\cF}{{\mathcal F}}
\newcommand{\cI}{{\mathcal I}}
\newcommand{\cM}{{\mathcal M}}
\newcommand{\cN}{{\mathcal N}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\Fq}{{{\mathbb F}_q}}
\newcommand{\F}{{{\mathbb F}}}
\newcommand{\kq}[1]{{{ {[#1]_q} }}}
\newcommand{\qb}[2]{{{ {\binom{#1}{#2}}_q }}}
\newcommand{\bin}[2]{{{ \binom{#1}{#2}}} }
\newcommand{\oc}[1]{{{ \overline{#1} }}}
\ncom{\noi}{\noindent}
\ncom{\bq}{\begin{equation}}
\ncom{\eq}{\end{equation}}
\ncom{\beqn}{\begin{eqnarray*}}
\ncom{\eeqn}{\end{eqnarray*}}
\ncom{\ba}{\begin{array}}
\ncom{\ul}{\underline}
\ncom{\ea}{\end{array}}
\ncom{\beq}{\begin{eqnarray}}
\ncom{\eeq}{\end{eqnarray}}
\ncom{\rar}{\rightarrow}
\ncom{\lrar}{\longrightarrow}
\ncom{\bc}{\begin{center}}
\ncom{\ec}{\end{center}}
\ncom{\bt}{\begin{theo}}
\ncom{\bcon}{\begin{conj}}
\ncom{\et}{\end{theo}}
\ncom{\econ}{\end{conj}}
\ncom{\bl}{\begin{lemm}}
\ncom{\el}{\end{lemm}}
\ncom{\bco}{\begin{coro}}
\ncom{\ds}{\displaystyle}
\ncom{\eco}{\end{coro}}
\ncom{\bp}{\begin{prop}}
\ncom{\ep}{\end{prop}}
\ncom{\bex}{\begin{exam}}
\ncom{\eex}{\end{exam}}
\ncom{\bexr}{\begin{exer}}
\ncom{\eexr}{\end{exer}}
\ncom{\bprob}{\begin{problems}}
\ncom{\eprob}{\end{problems}}
\ncom{\bd}{\begin{defi}}
\ncom{\ed}{\end{defi}}
\ncom{\brm}{\begin{rema}}
\ncom{\erm}{\end{rema}}
\ncom{\ol}{\overline}
\ncom{\wh}{\widehat}
\ncom{\pf}{\begin{proof}}
\ncom{\eprf}{\end{proof}}
\ncom{\be}{\begin{enumerate}}
\ncom{\ee}{\end{enumerate}}
\ncom{\seq}{\subseteq}
\newcommand{\inp}[2]{\langle {#1} ,\,{#2} \rangle}
\title[A $q$-analog of the adjacency matrix of the $n$-cube]{A $q$-analog of the adjacency matrix of the $n$-cube}
\author[\initial{S.} Ghosh]{\firstname{Subhajit} \lastname{Ghosh}}
\address{Bar-Ilan University\\
Department of Mathematics\\
Ramat-Gan\\
5290002 (Israel)}
\email{gsubhajit@alum.iisc.ac.in}
\author[\initial{M.} \middlename{K.} Srinivasan]{\firstname{Murali} \middlename{K.} \lastname{Srinivasan}}
\address{Indian Institute of Technology, Bombay\\
Department of Mathematics\\
Powai, Mumbai\\
400076 (India)}
\email{murali.k.srinivasan@gmail.com}
\thanks{The first named author is partially supported by the Israel science foundation grant $\#957/20$.}
\keywords{$n$-cube, $q$-analog}
\subjclass{05E18, 05C81, 20C30}
\begin{abstract}
Let $q$ be a prime power and define $(n)_q = 1+q+q^2+\cdots +q^{n-1}$,
for a nonnegative integer $n$. Let $B_q(n)$ denote the set
of all subspaces of $\mathbb F_q^n$,
the $n$-dimensional $\mathbb Fq$-vector space of all column vectors
with $n$ components.
Define a $B_q(n)\times B_q(n)$ complex matrix $M_q(n)$
with entries given by
\[
M_q(n)(X,Y) = \begin{cases}
1 & \text{if }Y\subseteq X, \dim(Y)= \dim(X)-1,\\
q^k & \text{if }X\subseteq Y, \dim(Y)=k+1, \dim(X)=k,\\
0 & \text{otherwise.}
\end{cases}
\]
We think of $M_q(n)$ as a $q$-analog of the
adjacency matrix of the $n$-cube.
We show that the eigenvalues of $M_q(n)$ are
\[
(n-k)_q - (k)_q \text{ with multiplicity } \binom{n}{k}_q,\;\;k=0,1,\ldots ,n,
\]
and we write down an explicit canonical eigenbasis of $M_q(n)$.
We give a weighted count of
the number of rooted spanning trees in the $q$-analog of the $n$-cube.
\end{abstract}
\dedicatory{To the memory of Chandan and beloved Lawson}
\datepublished{2023-06-19}
\begin{document}
\maketitle
\section{{Introduction}} \label{sec:intro}
One aspect of algebraic combinatorics is the study of
eigenvalues and eigenvectors of certain matrices
associated with posets and graphs. Among the most basic such examples is
the adjacency matrix of the $n$-cube, which
has an elegant spectral theory and arises in a variety of applications
(see ~{\cite{cst,st}}). This paper defines a
$q$-analog of this matrix, studies its spectral theory, and gives
an application to weighted counting of rooted spanning trees in the $q$-analog
of the $n$-cube.
Let $q$ be a prime power and define $(n)_q = 1+q+q^2+\cdots +q^{n-1}$,
for a nonnegative integer $n$. Let $B_q(n)$ denote the set
of all subspaces of $\F_q^n$,
the $n$-dimensional $\Fq$-vector space of all column vectors
with $n$ components.
The set of $k$-dimensional subspaces in~$B_q(n)$ is denoted $B_q(n,k)$
and its cardinality is the {\em $q$-binomial coefficient $\qb{n}{k}$}.
The {\em Galois number}
$$G_q(n)=\sum_{k=0}^n \qb{n}{k}$$
is the total number of subspaces in $B_q(n)$. The set $B_q(n)$ has
the structure of a graded poset of rank $n$, under inclusion.
Recall the definition of the adjacency matrix $M(n)$ of the $n$-cube: let
$B(n)$ denote the set of all subsets of $\{1,2,\ldots ,n\}$. The
rows and columns of $M(n)$ are indexed by elements of $B(n)$,
with the entry in row $S$, column $T$ equal to 1 if $|(S\setminus T)\cup
(T\setminus S)|=1$
and equal to 0 otherwise.
Define a $B_q(n)\times B_q(n)$ complex matrix $M_q(n)$ with entries given by
\begin{eqnarray}\label{eq:mt1}
M_q(n)(X,Y) &=& \begin{cases}
1 & \mbox{if }Y\seq X, \dim(Y)= \dim(X)-1,\\
q^k & \mbox{if }X\seq Y, \dim(Y)=k+1, \dim(X)=k,\\
0 & \mbox{otherwise.}
\end{cases}
\end{eqnarray}
We think of $M_q(n)$ as
{\em a $q$-analog of the adjacency matrix of the $n$-cube}.
Note that $M(n)$
is symmetric, has entries in $\{0,1\}$, and has all
row sums equal to $n$. The significance of the
definition above for the $q$-analog
comes from the fact that though
$M_q(n)$ lacks the first two properties
it does have all row sums equal.
Indeed, let $X\in B_q(n,k)$. Then the number of subspaces covering
$X$ is $(n-k)_q$ and the number of subspaces covered by $X$ is $(k)_q$
and so the sum of the entries of row $X$ of
$M_q(n)$ is $q^k(n-k)_q + (k)_q = (n)_q$.
A scaling (i.e., a diagonal similarity) of $M_q(n)$ is symmetric. Let $D_q(n)$ be the~$B_q(n)\times B_q(n)$
diagonal matrix with diagonal entry in row $X$, column $X$
given by~$\sqrt{q^{\bin{k}{2}}}$, where $k=\dim(X)$. Then for $X\in B_q(n,k)$,
$Y\in B_q(n,r)$ the entry in row~$X$, column $Y$ of $D_q(n)M_q(n)D_q(n)^{-1}$
is given by
\beqn
\lefteqn{\sqrt{q^{\bin{k}{2}}}\, M_q(n)(X,Y)\, \sqrt{q^{-\bin{r}{2}}}}\\
&=&\begin{cases}
\sqrt{q^{\bin{k}{2}}}\, q^k\, \sqrt{q^{-\bin{k+1}{2}}} =
\sqrt{q^k} & \mbox{if $X\seq Y$ and $r=k+1$,}\\
\sqrt{q^{\bin{k}{2}}} \sqrt{q^{-\bin{k-1}{2}}} =
\sqrt{q^{r}} & \mbox{if $Y\seq X$ and $r=k-1$,}\\
0 & \mbox{otherwise,}
\end{cases}\\
&=&\begin{cases}
\sqrt{q^{\min\{\dim(X),\dim(Y)\}}}&
\mbox{if $X\seq Y$ or $Y\seq X$, and $|\dim(X)-\dim(Y)|=1$,} \\
0 & \mbox{otherwise,}
\end{cases}
\eeqn
yielding a symmetric matrix. It follows that $M_q(n)$
is diagonalizable and that its eigenvalues
are real. In fact they are integral and the (eigenvalue, multiplicity)
pairs of $M_q(n)$ are a $q$-analog of those for $M(n)$; the eigenvalues of
$M(n)$ are $n-2k=(n-k)-(k)$ with multiplicity
$\binom{n}{k}$, $k=0,1,\ldots ,n$ (see~{\cite{cst,st}}).
\bt \label{mt1}
The eigenvalues of the matrix $M_q(n)$ are
$$(n-k)_q - (k)_q
\mbox{ with multiplicity } \qb{n}{k},\;\;k=0,1,\ldots ,n.$$
\et
We give two proofs of Theorem~\ref{mt1} in this paper. The first proof,
given in Section~\ref{sec:eigenvals}, is based on two basic results of
Terwilliger ~{\cite{t1,t2,t4}}. A result from ~{\cite{t1}} on the
existence of a symmetric Jordan basis with respect to the up operator,
together with formulas for the action of the up and down operators on this basis,
reduces Theorem~\ref{mt1}
to showing that the eigenvalues of $K_q(n)$,
a certain $(n+1)\times (n+1)$ tridiagonal matrix, are
$(n-k)_q - (k)_q,\;0\leq k \leq n$. The matrix
$K_q(n)$ is a $q$-analog
of the famous tridiagonal matrix $K(n)$ of
Mark Kac ~{\cite{a,k,tt}} (both these
matrices are defined in Section~\ref{sec:eigenvals}). Now $K_q(n)$ occurs in
Terwilliger's classification
of Leonard pairs ({\cite{t2, t4}}) and as such its eigenvalues/eigenvectors
were known (see, for example, Lemma~4.20 in ~{\cite{t3}}), completing
the first proof of Theorem~\ref{mt1}.
Another natural problem is to write down eigenvectors of $M_q(n)$.
For $X\in B_q(n)$ with $\dim(X)=k$ define
$$\pi(X) = \frac{q^{\bin{k}{2}}}{P_q(n)},
$$
where $P_q(n) =\prod_{k=0}^{n-1} (1+q^k)$.
We have
$$\sum_{X\in B_q(n)}\pi(X)\;=\;\frac{\sum_{k=0}^n q^{\bin{k}{2}}\qb{n}{k}}
{P_q(n)}\;=\;1$$
where the second equality follows by
the $q$-binomial theorem (so $\pi$ is a probability vector on $B_q(n)$).
Define an inner product on the (complex) vector space of column vectors
with components indexed by $B_q(n)$ as follows: given vectors $u,v$ define
\beq \label{inp}
\inp{u}{v}_\pi =\sum_{X\in B_q(n)}\ol{u(X)}v(X)\pi(X).
\eeq
Since $P_q(n)$ is independent of $k$,
the argument showing that $D_q(n)M_q(n)D_q(n)^{-1}$
is symmetric shows that $M_q(n)$ is
self-adjoint with respect
to the inner product~\eqref{inp}.
Recall that a classical result exhibits an explicit orthogonal eigenbasis
of $M(n)$ (under the standard inner product), see ~{\cite{cst,st}}. Up to
scalars, this basis is canonical in the sense that no choices are involved
in writing it down. Moreover, the product $M(n)v$, for $v$ in the eigenbasis,
can be evaluated easily, determining the eigenvalues of $M(n)$.
In Section~\ref{sec:eigenvecs} we extend this method to $M_q(n)$.
\bt \label{evectors}
There is an inductive procedure to write down a canonical eigenbasis
of $M_q(n)$, orthogonal with respect to the inner product~\eqref{inp}.
\et
In the course of proving Theorem~\ref{evectors} we also evaluate the
products $M_q(n)v$, for $v$ in the eigenbasis, thereby
giving an alternate proof of Theorem~\ref{mt1}.
Let us make a few informal remarks about the proof of Theorem~\ref{evectors}.
For the
matrix $M(n)$ one writes down an orthogonal eigenbasis, directly and
explicitly for each $n$. It is not clear how to extend
this direct approach to $M_q(n)$.
On the other hand, we can inductively understand the eigenbasis of $M(n)$ and then
try to extend that approach to $M_q(n)$. Roughly speaking, $M(n+1)$ can be
built using two copies of $M(n)$ and this allows us to write down an eigenbasis
of $M(n+1)$ given an eigenbasis of $M(n)$. The Goldman--Rota recurrence
for the Galois numbers ({\cite{gr,kc,ku}})
\beq \label{gri}
G_q(n+1) &=& 2G_q(n) + (q^n - 1)G_q(n-1),\;n\geq 1,\;\;
G_q(0)=1,\;G_q(1)=2,\eeq
suggests the possibility of
building $M_q(n+1)$ from two copies of $M_q(n)$ and $(q^n-1)$ copies of
$M_q(n-1)$ and using this to write down an eigenbasis of $M_q(n+1)$
given eigenbases of $M_q(n)$ and $M_q(n-1)$.
This is implemented in Section~\ref{sec:eigenvecs} using a linear algebraic
interpretation of the Goldman--Rota recurrence that was worked out
in ~{\cite{s3}} (and summarized in Section~\ref{sec:decomp} of the present paper).
The two copies of $M_q(n)$ occurring in $M_q(n+1)$ is along the same lines
as the $q=1$ case (although we need some powers of~$q$ not visible in the $q=1$
case, see~\eqref{ind} and cases (a), (b) in the proof
of Theorem~\ref{mt}).
The extra feature here is the $q^n-1$ copies of $M_q(n-1)$ in $M_q(n+1)$.
Here a central role is played by the
characters of the additive abelian group
$\F^n_q$. There is a copy of $M_q(n-1)$ inside $M_q(n+1)$ for every nontrivial
irreducible character of~$\F^n_q$, so $q^n-1$ copies in all. These introductory
remarks on Theorem~\ref{evectors} are continued at the beginning
of Section~\ref{sec:eigenvecs}.
We originally arrived at the matrix $M_q(n)$
through a reversible Markov chain with state space
$B_q(n)$, transition matrix $\frac{1}{(n)_q}M_q(n)$, and stationary distribution
$\pi$ (see ~{\cite{gs}}).
Since the spectral
theory of $M_q(n)$, as a $q$-analog of the spectral theory of $M(n)$,
is of independent interest we are presenting it separately
in this paper.
Another application concerns weighted enumeration of
rooted spanning trees in the $q$-analog of the $n$-cube.
Let us first recall
the remarkable product formula (see Example 9.12 in ~{\cite{st}}) for the
number of rooted spanning trees in the $n$-cube.
Let $C(n)$ denote the $n$-cube (i.e.,
the Hasse diagram of the poset $B(n)$ treated as a graph) and let
$\cF(n)$ denote the set of all rooted spanning trees of $C(n)$.
The Laplacian
eigenvalues of $C(n)$ are well known to be $2k,\;k=0,1,\ldots ,n$ with multiplicity
$\bin{n}{k}$. It thus follows from the Matrix-Tree theorem that the number of
rooted spanning trees of $C(n)$ is given by
\beq \label{hc}
\sum_{F\in \cF(n)} 1&=&\prod_{k=1}^n (2k)^{\bin{n}{k}}.
\eeq
The {\em $q$-analog $C_q(n)$} of $C(n)$ is defined to be the Hasse diagram
of $B_q(n)$ treated as a graph (note that $M_q(n)$ is not the adjacency
matrix of the graph $C_q(n)$).
The eigenvalues of the Laplacian of $C_q(n)$ are not known
(note that $C_q(n)$ is not regular) but it was shown in ~{\cite{s2}} that
the product of the nonzero eigenvalues of the Laplacian is more tractable and
led to a product formula for the number of spanning trees
of $C_q(n)$, although the individual terms in this product are
not explicitly
given but only as a positive combinatorial sum.
Here we obtain an explicit $q$-analog of~\eqref{hc} by a weighted
count of the rooted spanning trees of $C_q(n)$.
Let $F\in \cF_q(n)$, the set of all
rooted spanning trees of $C_q(n)$. Orient every edge
of~$F$ by pointing it towards the root. Let $e=(X,Y)$ be an oriented edge
of $F$. We say $e$ is {\em{spin up}} if $\dim(Y)=\dim(X)+1$ and is {\em{spin down}}
if $\dim(Y)=\dim(X)-1$. The {\em{weight}} of $F$ is defined by
\beqn
w(F)&=&\sum_{(X,Y)}\dim(X),
\eeqn
where the sum is over all spin up oriented edges of $F$. In Section~\ref{sec:trees} we prove
the following generalization of~\eqref{hc}
(the proof can be read at this point, assuming Theorem~\ref{mt1}).
\bt \label{qct} We have
$$\sum_{F\in\cF_q(n)}q^{w(F)} = \prod_{k=1}^n ((1+q^{n-k})(k)_q)^{\qb{n}{k}}.
$$
\et
\section{{Eigenvalues of \texorpdfstring{$M_q(n)$}{Mq(n)} }} \label{sec:eigenvals}
The spectral theory of $M_q(n)$ goes hand in hand with that of
a $q$-analog of the Kac matrix.
Recall that the Kac matrix is a $(n+1)\times (n+1)$ tridiagonal matrix $K(n)$
with diagonal $(0,0,\ldots ,0)$, subdiagonal $(1,2,\ldots ,n)$
and superdiagonal $(n,n-1,\ldots ,1)$:
\[K(n) = \left[\ba{cccccc}
0&n&&&&\\
1&0&n-1&&&\\
&2&0&n-2&&\\
&&\ddots&\ddots&\ddots&\\
&&&n-1&0&1\\
&&&&n&0
\ea\right].\]
The eigenvalues of $K(n)$ are $n-2k, k=0,1,\ldots ,n$, and
its eigenvectors have been written down
(see ~{\cite{a,cst,ek,k,tt}}).
We define the $q$-analog of the Kac matrix to be
the $(n+1)\times (n+1)$ tridiagonal matrix $K_q(n)$
with diagonal $(0,0,\ldots ,0)$, subdiagonal $((1)_q,(2)_q,\ldots ,(n)_q)$ and superdiagonal $((n)_q,q(n-1)_q,\ldots ,q^{n-1}(1)_q)$:
\[K_q(n) = \left[\ba{cccccc}
0&(n)_q&&&&\\
(1)_q&0&q(n-1)_q&&&\\
&(2)_q&0&q^2(n-2)_q&&\\
&&\ddots&\ddots&\ddots&\\
&&&(n-1)_q&0&q^{n-1}(1)_q\\
&&&&(n)_q&0
\ea\right].\]
More formally, let us index the rows and columns of $K_q(n)$ by the set
$\{0,1,2,\ldots ,n\}$.
If $c_0,c_1,\ldots ,c_n$ denote column vectors
in $\F_q^{n+1}$ with $c_i$ having a 1 in the component
indexed by $i$ and 0's
elsewhere (and we set $c_{-1}=c_{n+1}=0$)
then, for $0\leq k \leq n$, column $k$ of $K_q(n)$
is
\beq \label{ctm}
&(k+1)_q\;c_{k+1} + q^{k-1} (n-k+1)_q\;c_{k-1}.&
\eeq
We now discuss the significance of $K_q(n)$ for studying $M_q(n)$.
The proper framework for studying this
are the up (and down) operators on the poset of subspaces.
For a finite set $S$, we denote the complex vector space with $S$
as basis by $\C[S]$.
We denote by $r$ the rank function (given by dimension) of the graded
poset $B_q(n)$.
Then we have (vector space direct sum)
$$\C[B_q(n)]=\C[B_q(n,0)]\oplus
\C[B_q(n,1)]\oplus \cdots \oplus\C[B_q(n,n)].$$
An element $v\in \C[B_q(n)]$ is {\em homogeneous} if
$v\in \C[B_q(n,i)]$ for some $i$,
and if~$v\not= 0$, we extend the notion of rank to nonzero
homogeneous elements by writing $r(v)=i$. For $0\leq k \leq n$,
the {\em $k^{th}$ up operator} $U_{n,k}:\C[B_q(n)]\rar \C[B_q(n)]$
is defined, for $X\in B_q(n)$, by $U_{n,k}(X)=0$ if $\dim(X)\not=k$ and
$U_{n,k}(X)= \sum_{Y} Y$,
where the sum is over all $Y\in B_q(n)$ covering $X$, if $\dim(X)=k$.
Similarly we define the {\em $k^{th}$ down operator}
$D_{n,k}:\C[B_q(n)]\rar \C[B_q(n)]$ (we have $U_{n,n}=D_{n,0}=0$).
Set $U_n=U_{n,0}+U_{n,1}+\cdots +U_{n,n}$
and $D_n=D_{n,0}+D_{n,1}+\cdots +D_{n,n}$, called, respectively,
the {\em up and down} operators on $\C[B_q(n)]$.
If we think of the elements of $\C[B_q(n)]$ as column vectors
with components
indexed by the {\em standard basis} elements $B_q(n)$ then
$M_q(n)$ is the matrix of the operator
$$\cA_q(n) = U_n +\sum_{k=0}^n q^{k-1}D_{n,k}$$
with respect to the basis $B_q(n)$.
For $0\leq k \leq n$, define $s_k\in \C[B_q(n,k)]$ by
$$ s_k = \sum_{X\in B_q(n,k)} X,$$
and define $R_q(n)$ to be the subspace of $\C[B_q(n)]$ spanned by $s_0,s_1,\ldots
, s_n$. Elements of $R_q(n)$ are called {\em radial vectors}. Clearly, $R_q(n)$
is closed under $\cA_q(n)$ and $\dim(R_q(n))=n+1$. We have
\beqn
\cA_q(n)(s_k)= (k+1)_q\;s_{k+1} + q^{k-1}(n-k+1)_q\;s_{k-1},\;\;0\leq k \leq n.
\eeqn
It follows from~\eqref{ctm}
that the matrix of $\cA_q(n): R_q(n)\rar R_q(n)$ with respect to the basis
$\{s_0,\ldots ,s_n\}$ is $K_q(n)$.
Thus, knowing the eigenvalues of $K_q(n)$ would at least
tell us some of the eigenvalues of $M_q(n)$. The eigenvalues and eigenvectors
of $K_q(n)$ have been determined by Terwilliger ~{\cite{t3}} (we shall
not use the eigenvector information given in the result below
in this paper).
\bt \label{mt2}
(i) The eigenvalues of $K_q(n)$ are
$$(n-k)_q - (k)_q,\;k=0,1, \ldots ,n.$$
(ii) For $0\leq k \leq n$, there is a right eigenvector of $K_q(n)$
corresponding to the eigenvalue $(n-k)_q - (k)_q$ whose component
$i,\;0\leq i \leq n$ is given by
$$ _3\phi_2 \left( \ba{c} q^{-i}, q^{-k}, -q^{k-n}\\0, q^{-n} \ea
\; \vline \; q, q
\right)$$
where the basic hypergeometric series notation is from ~{\cite{gr1}}.
\et
\pf
This is Lemma 4.20 in ~{\cite{t3}} (replace $b$ by $q$,
$d$ by $n$, and $j$ by $n-k$).
Part (i) also follows from
Theorem 2 in Johnson ~{\cite{j}} (by
taking $a=z=1$ and $h=k=0$). \eprf
To show that there are no other eigenvalues of $M_q(n)$ and that the eigenvalue
multiplicities are as claimed in Theorem~\ref{mt1} we shall use
another result of Terwilliger ~{\cite{t1}}.
A {\em symmetric chain} in $\C[B_q(n)]$ is a sequence
\beq \label{gjc}
&s=(v_k,\ldots ,v_{n-k}),\;\;\;k\leq n/2,&
\eeq
of nonzero homogeneous elements of $\C[B_q(n)]$
such that
\begin{itemize}
\item $r(v_i)=i$ for $i=k,\ldots ,n-k$.
\item $U_n(v_i)$ is a nonzero scalar multiple of $v_{i+1}$, for
$i=k,\ldots , n-k-1$ and $U_n(v_{n-k})=0$.
\item $D_n(v_{i+1})$ is a nonzero scalar multiple of $v_i$ for
$i=k,\ldots , n-k-1$ and $D_n(v_k)=0$.
\end{itemize}
Note that the
elements of the sequence $s$ are linearly independent, being nonzero and of
different ranks.
We say that $s$ {\em
starts} at rank $k$ and {\em ends} at rank $n-k$. Note that the subspace spanned
by the elements of $s$ is closed under $U_n,D_n$ and also $\cA_q(n)$.
The following result was proved (in an equivalent form)
by Terwilliger ~{\cite{t1}} (see Item~5 of Theorem~3.3 on top
of page 208). For a proof
using Proctor's $\mathfrak{sl}(2,\C)$ technique ~{\cite{p}} see Theorem 2.1
in ~{\cite{s2}} (where also the result is stated differently
but in an equivalent form to that given below).
\bt \label{sjb}
There exists a basis $T_q(n)$ of $\C[B_q(n)]$ such that
\begin{enumerate}
\item $T_q(n)$ is a disjoint union of symmetric chains in $\C[B_q(n)]$.
\item Let $0\leq k \leq n/2$ and let $(v_k,\ldots ,v_{n-k})$ be any
symmetric chain in $T_q(n)$ starting at rank $k$ and ending at rank $n-k$.
Then
\beqn
U_n(v_u)&=& q^k(u+1-k)_q\;v_{u+1},\;k\leq u < n-k.\\
D_n(v_{u+1})&=& (n-k-u)_q\;v_u,\;k\leq u < n-k.
\eeqn
\end{enumerate}
\et
We now give the
\pf[Proof of Theorem~\ref{mt1}]
Observe the following.
(i) The number of symmetric chains in $T_q(n)$ starting at rank $k$ and ending at
rank $n-k$, for $0\leq k \leq n/2$, is $\qb{n}{k} - \qb{n}{k-1}$.
(ii) Let $s=(v_k,\ldots ,v_{n-k})$ be a symmetric chain in $T_q(n)$ starting
at rank $k$, where
$0\leq k \leq n/2$. Then the subspace spanned by $\{v_k,\ldots ,v_{n-k}\}$
is closed under $\cA_q(n)$ and, by Theorem~\ref{sjb},
the matrix of $\cA_q(n)$
with respect to the basis $s$ is $q^k K_q(n-2k)$.
(iii) By Theorem~\ref{mt2} the eigenvalues of $q^k K_q(n-2k)$ are
\beqn
\lefteqn{ q^k((n-2k-i)_q - (i)_q),\;i=0,1,\ldots ,n-2k}\\
&=& ((n-i)_q - (i)_q),\;i=k,\ldots ,n-k.
\eeqn
(iv) It now follows from items (i), (ii), (iii) above that the eigenvalues
of $\cA_q(n)$ are
\beqn
(n-j)_q - (j)_q,\;j=0,\ldots ,n,
\eeqn
with respective multiplicities
\beqn \sum_{i=0}^{\min\{j,n-j\}} \qb{n}{i} - \qb{n}{i-1} = \qb{n}{j}.
\eeqn
That completes the proof. \eprf
\section{{A decomposition of \texorpdfstring{$\C[B_q(n)]$} {CBq(n)} }} \label{sec:decomp}
In this and the next section we give proofs of Theorems~\ref{mt1}
and~\ref{evectors} by inductively writing down
an eigenbasis for the operator $\cA_q(n)$.
This is based on
a direct sum decomposition of the vector space $\C[B_q(n)]$ that was given
in the paper ~{\cite{s3}}. This decomposition yields a linear
algebraic interpretation
of the Goldman--Rota recurrence
(see equations~\eqref{d1},~\eqref{d2},~\eqref{grd}
and Remark~\ref{remark1})
and is
of independent interest.
In ~{\cite{s3}} it was used to inductively
write down an explicit eigenbasis for the Bose--Mesner algebra
of the Grassmann scheme. Here
we recall the relevant definitions and results from ~{\cite{s3}}. All the
omitted proofs may be found in Section~2 of ~{\cite{s3}}.
We can write down the Goldman--Rota identity
in terms of the $q$-binomial coefficients,
\beq \label{nsw}
\qb{n+1}{k} &=& \qb{n}{k} + \qb{n}{k-1} + (q^n - 1)\qb{n-1}{k-1},\;n,k\geq
1,\eeq
with $\qb{0}{k}=\delta(0,k)$ and $\qb{n}{0}=1$.
Note that~\eqref{gri} follows by summing~\eqref{nsw} over $k$.
We shall now give a linear algebraic interpretation to~\eqref{gri} and
\eqref{nsw}. Denote
the standard basis vectors of $\F^n_q$ by the column vectors $e_1,\ldots ,e_n$.
We identify $\F_q^k$, for $k