\documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.37}{21(1)}{2014} \usepackage{amsthm,amsmath,amssymb} \usepackage{graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \sloppy \allowdisplaybreaks \parskip 1ex \usepackage{euscript} \let\scr=\EuScript \newtheorem{thm}{Theorem}[section] \newtheorem{con}{Conjecture}[section] \newtheorem{lemma}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{pro}[thm]{Proposition} \newtheorem{example}[thm]{Example} \newtheorem{definition}[thm]{Definition} \newcommand{\tab}{\mbox{Tab }} \newtheorem{remark}[thm]{Remark} \newtheorem{Algorithm}[thm]{Algorithm} \newcommand{\DPn}{\mathsf{DP(n)}} \newcommand{\EDn}{\widehat{\mathsf{DP}}{(n)}} \newcommand{\ESn}{\widehat{\mathsf{DS}}{(n)}} \newcommand{\OP}{\mathsf{O(P)}} \newcommand{\Cn}{\mathsf{C(n)}} \newcommand{\Snr}{\mathsf{S(n,r)}} \newcommand{\Snt}{\mathsf{S(n,2)}} \newcommand{\Sn}{\mathsf{S(n)}} \newcommand{\DSn}{\mathsf{DS(n)}} \newcommand{\DSmn}{\mathsf{DS(m,n)}} \newcommand{\DPmn}{\mathsf{DP(m,n)}} \newcommand{\Kn}{\mathsf{K(n)}} \newcommand{\TPn}{\mathsf{TP(n)}} \newcommand{\av}{{\cal A}} \newcommand{\pv}{{\cal P}} \newcommand{\Fn}{\mathsf{F(n)}} \newcommand{\comment}[1]{} \newcommand{\cIq}{{\mathcal I}_q} \newcommand{\cNq}{{\mathcal N}_q} \newcommand{\cB}{\mathcal B} \newcommand{\cS}{\mathcal S} \newcommand{\cH}{\mathcal H} \newcommand{\RE}{{\mathbb R}} \newcommand{\N}{{\mathbb N}} \newcommand{\Aq}{A_q} \newcommand{\Bq}{B_q} \newcommand{\Vq}{V_q} \newcommand{\Cq}{C_q} \newcommand{\Bfq}{B_{{\mathbb F}_q}} \newcommand{\Cfq}{C_{{\mathbb F}_q}} \newcommand{\Fq}{{\mathbb F}_q} \newcommand{\C}{{\mathbb C}} \newcommand{\Rl}{{\mathbb R}_{\leq}} \newcommand{\pr}{\parallel} \newcommand{\spec}{\mbox{spec}} \newcommand{\kq}[1]{{{ {[#1]_q} }}} \newcommand{\qb}[2]{{{ {{#1}\brack {#2}}_q }}} \newcommand{\bin}[2]{{{ {#1}\choose {#2}}} } \newcommand{\bfx}[1]{{{\bf{#1}}}} \newcommand{\oc}[1]{{{ \overline{#1} }}} \newcommand{\I}{{\cal{I}}} \def\thetheorem{\thesection.\arabic{thm}} \def\thedefinition{\thechapter.\arabic{definition}} \def\theremark{\thechapter.\arabic{remark}} \def\thecorollary{\thechapter.\arabic{cor}} \def\thelemma{\thechapter.\arabic{lemma}} \def\theproposition{\thechapter.\arabic{pro}} \def\theexample{\thechapter.\arabic{example}} \def\theAlgorithm{\thechapter.\arabic{Algorithm}} \newcommand{\ncom}{\newcommand} \ncom{\ns}{\normalsize} \ncom{\la}{\lambda} \ncom{\bm}{\boldmath} \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{\nno}{\nonumber} \ncom{\hs}{\mbox{\hspace{.25cm}}} \ncom{\rar}{\rightarrow} \ncom{\Rar}{\Rightarrow} \ncom{\noin}{\noindent} \ncom{\bc}{\begin{center}} \ncom{\ec}{\end{center}} \ncom{\sz}{\scriptsize} \ncom{\fpd}{\Phi(\pi^{'})} \ncom{\fp}{\Phi(\pi) } \ncom{\nk}{\left< \begin{array}{c} n\\k \end{array} \right>} \ncom{\nd}{1^{'},2^{'},\cdots,n^{'}} \ncom{\R}{I\!\!R} \ncom{\de}{\bigtriangleup (F_{2n},\leq)} \ncom{\del}{\bigtriangleup} \ncom{\cov}{<\!\!\!\!\cdot } \ncom{\bt}{\begin{thm}} \ncom{\bcon}{\begin{con}} \ncom{\et}{\end{thm}} \ncom{\econ}{\end{con}} \ncom{\bl}{\begin{lemma}} \ncom{\el}{\end{lemma}} \ncom{\bco}{\begin{cor}} \ncom{\ds}{\displaystyle} \ncom{\eco}{\end{cor}} \ncom{\bp}{\begin{pro}} \ncom{\ep}{\end{pro}} \ncom{\bex}{\begin{example}} \ncom{\eex}{\end{example}} \ncom{\bd}{\begin{definition}} \ncom{\ed}{\end{definition}} \ncom{\brm}{\begin{remark}} \ncom{\erm}{\end{remark}} \ncom{\bal}{\begin{Algorithm}} \ncom{\eal}{\end{Algorithm}} \ncom{\ol}{\overline} \ncom{\wh}{\widehat} \ncom{\pf}{\noi {\bf Proof }} \ncom{\be}{\begin{enumerate}} \ncom{\ee}{\end{enumerate}} \ncom{\s}{\subset} \ncom{\T}{{\cal T}} \ncom{\B}{{\cal B}} \ncom{\A}{{\cal A}} \ncom{\Z}{{\cal Z}} \title{\bf The Goldman-Rota identity and the Grassmann scheme} \author{Murali K. Srinivasan \\ \small Department of Mathematics\\[-0.8ex] \small Indian Institute of Technology, Bombay\\[-0.8ex] \small Powai, Mumbai 400076, India\\ \small \texttt{mks@math.iitb.ac.in},\,\,\, \texttt{murali.k.srinivasan@gmail.com} } \begin{document} \date{\dateline{Jul 8, 2013}{Feb 15, 2014}{Feb 21, 2014} \\{\small Mathematics Subject Classifications: 05E25, 05E30.}} \maketitle \begin{center}{\em To the memory of Kaala, BMW, and $\infty$}\end{center} \begin{abstract} We inductively construct an explicit (common) orthogonal eigenbasis for the elements of the Bose-Mesner algebra of the Grassmann scheme. The key step is a constructive, linear algebraic interpretation of the Goldman-Rota recurrence for the number of subspaces of a finite vector space. This interpretation shows that the up operator on subspaces has an explicitly given recursive structure. Using the interpretation above we inductively construct an explicit orthogonal symmetric Jordan basis with respect to the up operator and write down the singular values, i.e., the ratio of the lengths of the successive vectors in the Jordan chains. The collection of all vectors in this basis of a fixed rank $m$ forms a (common) orthogonal eigenbasis for the elements of the Bose-Mesner algebra of the Grassmann scheme of $m$-dimensional subspaces. We also pose a bijective proof problem on the spanning trees of the Grassmann graphs. \end{abstract} {{\bf \section { Introduction }}} This paper presents {\em constructive} and {\em explicit} proofs of two basic linear algebraic results on the subspace lattice. We begin by recalling two important {\em existence} results on subspaces. Let $P$ be a finite {\em graded poset} with {\em rank function} $r: P\rar {\mathbb N}=\{0,1,2,\ldots \}$ (our poset terminology follows \cite{st2}). The {\em rank} of $P$ is $r(P)=\mbox{max}\{r(x): x\in P\}$ and, for $i=0,1,\ldots ,r(P)$, $P_i$ denotes the set of elements of $P$ of rank $i$. For a subset $S\subseteq P$, we set $\mbox{rankset}(S) = \{r(x):x\in S\}$. A {\em symmetric chain} in a graded poset $P$ is a sequence $$(p_1,p_2,\ldots ,p_h)$$ of elements of $P$ such that $p_i$ covers $p_{i-1}$, for $i=2,\ldots ,h$ and $r(p_1)+r(p_h)=r(P)$, if $h\geq 2$, or else $2r(p_1)=r(P)$, if $h=1$. A {\em symmetric chain decomposition} (SCD) of a graded poset $P$ is a decomposition of $P$ into pairwise disjoint symmetric chains. Let $B(n)$ denote the collection of all subsets of the set $\{1,2,\ldots ,n\}$. Partially order $B(n)$ by inclusion. Let $\Fq^n$ denote the $n$-dimensional vector space of all column vectors of length $n$ over $\Fq$ and let $\Bq(n)$ denote the collection of all subspaces of $\Fq^n$. Partially order $\Bq(n)$ by inclusion. Define $\kq{k}=1+q+q^2+\cdots +q^{k-1}$, $k\in \N$. For $0\leq k \leq n$, the {\em $q$-binomial coefficient} $$\qb{n}{k} = \frac{\kq{1}\kq{2}\cdots \kq{n}}{\kq{1}\cdots \kq{k}\kq{1}\cdots \kq{n-k}}$$ denotes the number of $k$-dimensional subspaces in $\Bq(n)$ and the total number of subspaces is the {\em Galois number} $$G_q(n)=\sum_{k=0}^n \qb{n}{k}.$$ The following result was proved in \cite{g} using network flow techniques. % \bt \label{griggs} There exists a symmetric chain decomposition of the graded poset $\Bq(n)$. \et % Although Theorem \ref{griggs} is interesting in itself one of its main motivations was that the existence of a SCD of a graded poset $P$ is a stronger property than $P$ being strongly Sperner, a fact that was already known for $\Bq(n)$ (see \cite{e}). Theorem \ref{griggs} has a linear analog, which we now state. For a finite set $S$, let $V(S)$ denote the complex vector space with $S$ as basis. Let $v=\sum_{x\in S}\alpha_x\,x,\,\alpha_x\in \C$ be an element of $V(S)$. By the {\em support} of $v$ we mean the subset $\{x\in S : \alpha_x\not= 0\}$. Let $P$ be a graded poset with $n=r(P)$. Then we have \[ V(P)=V(P_0)\oplus V(P_1) \oplus \cdots \oplus V(P_n)\] (vector space direct sum). An element $v\in V(P)$ is {\em homogeneous} if $v\in V(P_i)$ for some $i$, and if $v\not= 0$, we extend the notion of rank to nonzero homogeneous elements by writing $r(v)=i$. Given an element $v\in V(P)$, write $v=v_0 + \cdots +v_n$, where $v_i \in V(P_i),\;0\leq i \leq n$. We refer to the $v_i$ as the {\em homogeneous components} of $v$. A subspace $W\subseteq V(P)$ is {\em homogeneous} if it contains the homogeneous components of each of its elements. For a homogeneous subspace $W\subseteq V(P)$ we set \[ \mbox{rankset}(W)=\{r(v) : v \mbox{ is a nonzero homogeneous element of } W\}.\] The {\em up operator} $U:V(P)\rar V(P)$ is defined, for $x\in P$, by $U(x)= \sum_{y} y$, where the sum is over all $y$ covering $x$. We denote the up operator on $V(\Bq(n))$ by $U_n$. For a finite vector space $X$ over $\Fq$ we denote by $\Bq(X)$ the set of all subspaces of $X$ and we denote by $U_X$ the up operator on $V(\Bq(X))$. Let $\langle , \rangle$ denote the standard inner product on $V(P)$, i.e., $\langle x,y \rangle = \delta (x,y)$ (Kronecker delta), for $x,y\in P$. The {\em length} $\sqrt{\langle v, v \rangle }$ of $v\in V(P)$ is denoted $\pr v \pr$. We give $V(\Bq(n))$ (and $V(\Bq(X))$ for a finite vector space $X$ over $\Fq$) the standard inner product. Let $P$ be a finite graded poset with rank function $r$. A {\em graded Jordan chain} in $V(P)$ is a sequence \beq \label{gjc} &s=(v_1,\ldots ,v_h)& \eeq of nonzero homogeneous elements of $V(P)$ such that $U(v_{i-1})=v_i$, for $i=2,\ldots h$, and $U(v_h)=0$ (note that the elements of this sequence are linearly independent, being nonzero and of different ranks). We say that $s$ {\em starts} at rank $r(v_1)$ and {\em ends} at rank $r(v_h)$. A {\em graded Jordan basis} of $V(P)$ is a basis of $V(P)$ consisting of a disjoint union of graded Jordan chains in $V(P)$. The graded Jordan chain (\ref{gjc}) is said to be a {\em symmetric Jordan chain} (SJC) if the sum of the starting and ending ranks of $s$ equals $r(P)$, i.e., $r(v_1) + r(v_h) = r(P)$ if $h\geq 2$, or $2r(v_1)= r(P)$ if $h=1$. A {\em symmetric Jordan basis} (SJB) of $V(P)$ is a basis of $V(P)$ consisting of a disjoint union of symmetric Jordan chains in $V(P)$. The following result was proved in \cite{t} using \cite{du}. % \bt \label{terwilliger} There exists an orthogonal symmetric Jordan basis $T_q(n)$ of $V(\Bq(n))$. Let $0\leq k \leq n/2 $ and let $(x_k,\ldots ,x_{n-k})$ be any symmetric Jordan chain in $T_q(n)$ starting at rank $k$ and ending at rank $n-k$. Then we have, for $k\leq u < n-k$, \beq \label{sv'} \frac{\pr x_{u+1} \pr}{\pr x_u \pr} & = & \sqrt{q^k\kq{u+1-k}\kq{n-k-u}}\;\,. \eeq \et See \cite{sr2} for a proof of Theorem \ref{terwilliger} based on the ${\mathfrak {sl}}(2,\C)$ method \cite{p}. Very closely related results are shown in \cite{d2,st1,mp2,bvp}. The numbers on the right hand side of (\ref{sv'}) are called the {\em singular values} of the up operator. These are important for applications. Theorem \ref{terwilliger} has several applications. In \cite{sr3} we showed that the commutant of the $GL(n,\Fq)$ action on $V(\Bq(n))$ block diagonalizes with respect to the orthonormal basis given by the normalization of $T_q(n)$ and we used (\ref{sv'}) to make this block diagonalization explicit, thereby obtaining a $q$-analog of the formula from \cite{s} for explicit block diagonalization of the commutant of the symmetric group action on $V(B(n))$. This includes, as a special case, a formula for the eigenvalues of the elements of the Bose-Mesner algebra of the Grassmann scheme \cite{d1,cst}. For other approaches to explicit block diagonalization see \cite{s,mp1,mp2,bvp}, the first and last of which give applications to bounds on codes using semidefinite programming. In \cite{sr2} we used (\ref{sv'}) to give a positive combinatorial formula for the number of spanning trees of the $q$-analog of the $n$-cube and to show that the Laplacian eigenvalues of the Grassmann graphs, known in principle since \cite{d1}, admit an elegant closed form. For another approach to the Laplacian eigenvalues of the Grassmann graphs see \cite{mp2}. At the end of this paper we pose a bijective proof problem on spanning trees of the Grassmann graphs. It is natural to ask for a constructive proof of Theorem \ref{griggs} and this was done in the beautiful paper \cite{vv}. The underlying premise of this paper is that it is equally natural to ask for a constructive proof of Theorem \ref{terwilliger}. The problem of constructing an explicit SJB should be put on an equal footing with the problem of constructing an explicit SCD (``More people should get used to considering formal sums of combinatorial objects as being as natural to deal with as individual objects", quote from \cite{be}) and in Section 3 we prove the following result. \bt \label{mt3} There is an algorithm to inductively construct an explicit orthogonal symmetric Jordan basis $J_q(n)$ of $V(\Bq(n))$. When expressed in the standard basis the vectors in $J_q(n)$ have coefficients that are integral multiples of $q${\em th} roots of unity. In particular, the coefficients are integral when $q=2$. Let $0\leq k \leq n/2 $ and let $(x_k,\ldots ,x_{n-k})$ be any symmetric Jordan chain in $J_q(n)$ starting at rank $k$ and ending at rank $n-k$. Then we have, for $k\leq u < n-k$, \beq \label{sv} \frac{\pr x_{u+1} \pr}{\pr x_u \pr} & = & \sqrt{q^k\kq{u+1-k}\kq{n-k-u}}\;\,. \eeq \et % A standard argument (recalled in Section 3) shows that the set $\{v\in J_q(n) : r(v)=m\}$ forms a common orthogonal eigenbasis for the elements of the Bose-Mesner algebra of the Grassmann scheme of $m$-dimensional subspaces. Explicit eigenvectors for the Johnson scheme (the $q=1$ case of the Grassmann scheme) have been well studied. See, for example, \cite{gj,gll,k,n,sr1}. The approach in \cite{gj,gll,k,n} produces integral eigenvectors with coefficients in $\{-1,0,1\}$ while the approach in \cite{sr1} produces orthogonal integral eigenvectors, with coefficients not necessarily in $\{-1,0,1\}$ (as remarked in \cite{k} it is not possible to simultaneously satisfy both requirements, i.e., orthogonality and coefficients in $\{-1,0,1\}$). Substituting $q=1$ in Theorem \ref{mt3} we recover the explicit orthogonal SJB of $V(B(n))$ constructed in \cite{sr1}. This basis was given a representation theoretic characterization in \cite{sr1}, namely, that it is the canonically defined symmetric Gelfand-Tsetlin basis of $V(B(n))$. Similarly, the basis $J_q(n)$ should also be studied from a representation theoretic viewpoint. We hope to return to this later. Our proof of Theorem \ref{mt3} proceeds via another constructive result on the recursive structure of the up operator on subspaces. It is an elementary observation that the up operator (or equivalently, incidence matrices) on subsets of a $n+1$-set can be built from two copies of the up operator on subsets of a $n$-set. We extend this inductive approach to the subspace lattice. A classical identity of Goldman and Rota suggests that the up operator on subspaces of a $n+1$-dimensional vector space over $\Fq$ can be built from two copies of the up operator in dimension $n$ and $q^n-1$ copies of the up operator in dimension $n-1$. Let us make this precise. We have $|B(n)| = 2^n$ and the identity $2^{n+1}=2\cdot 2^n$ has the following poset theoretic interpretation: we can write $B(n+1)$ as a disjoint union $B(n+1) = B(n) \cup [\{n+1\}, \{1,\ldots ,n+1\}]$, where the interval $[\{n+1\}, \{1,\ldots ,n+1\}]$ is order isomorphic to $B(n)$. The Goldman-Rota identity \cite{gr,kc,nsw} is the recursion \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 % We identify $\Fq^n$ with the subspace of all vectors in $\Fq^{n+1}$ with last component zero. Put $t=q^n - 1$. Motivated by the $B(n)$ case we can ask for the following poset theoretic interpretation of (\ref{gri}): is it possible to write $\Bq(n+1)$ as a disjoint union \beq \label{du} \Bq(n+1) &=& \Bq(n) \cup S_0 \cup S_1 \cup \cdots \cup S_t , \eeq where $S_0,\ldots ,S_t$ are intervals in $\Bq(n+1)$, with $S_0$ order isomorphic to $\Bq(n)$ and $S_1,\ldots ,S_t$ order isomorphic to $\Bq(n-1)$. At least for $q=2$ and $n\geq 4$ the answer is no, as shown in \cite{hh}. We show that we can get a poset theoretic interpretation of (\ref{gri}) by considering a linear analog of (\ref{du}). Moreover, the linear analog of the decomposition (\ref{du}) can be explicitly given. Let $(V,f)$ be a pair consisting of a finite dimensional vector space $V$ (over $\C$) and a linear operator $f$ on $V$. Let $(W,g)$ be another such pair. By an isomorphism of pairs $(V,f)$ and $(W,g)$ we mean a linear isomorphism $\theta : V \rar W$ such that $\theta(f(v)) = g(\theta(v)),\;v\in V$. We prove the following result on the recursive structure of the pair $(V(\Bq(n)),U_n)$ in Section 2. This result is used in Section 3 to construct the orthogonal SJB $J_q(n)$. \bt \label{grv} Set $t=q^n - 1$. There is an explicit orthogonal direct sum decomposition \beq \label{odsd} V(\Bq(n+1)) &=& V(\Bq(n)) \oplus W(0) \oplus W(1) \oplus \cdots \oplus W(t), \eeq where \noi (i) $W(0),\ldots ,W(t)$ are $U_{n+1}$-closed (i.e., closed under the action of $U_{n+1}$) homogeneous subspaces of $V(\Bq(n+1))$ with $\mbox{rankset}\,(W(0))=\{1,\ldots ,n+1\}$ and $\mbox{rankset}\,(W(i))=\{1,\ldots ,n\},$ for $i=1,\ldots ,t$. \noi (ii) $V(\Bq(n)) \oplus W(0)$ is $U_{n+1}$-closed and there is an explicit linear map $\theta_n : V(\Bq(n)) \rar W(0)$ that is an isomorphism of pairs $(V(\Bq(n)), q U_n)$ and $(W(0),U_{n+1})$, sending homogeneous elements to homogeneous elements, increasing rank by one and satisfying \beq \label{ti} U_{n+1}(v) &=& U_n(v) + \theta_n(v),\,\,v\in V(\Bq(n)), \\ \label{ti1} \langle \theta_n(w), \theta_n(v) \rangle &=& q^{n-k} \langle w,v\rangle,\,\,w,v\in V(\Bq(n)_k),\,0\leq k \leq n. \eeq \noi (iii) For $i=1,\ldots ,t$ there is an explicit linear map $\gamma_{n-1}(i): V(\Bq(n-1)) \rar W(i)$ that is an isomorphism of pairs $(V(\Bq(n-1)), U_{n-1})$ and $(W(i),U_{n+1})$, sending homogeneous elements to homogeneous elements, increasing rank by one and satisfying \beq \label{ti2} \langle \gamma_{n-1}(i)(w), \gamma_{n-1}(i)(v) \rangle &=& q^{n+k} \langle w,v\rangle,\,\,w,v\in V(\Bq(n-1)_k),\,0\leq k \leq n-1. \eeq \et \noi {\bf Remark} For $v\in V(\Bq(n)_k), \;0\leq k \leq n$, $\;w\in V(\Bq(n-1)_k), \;0\leq k \leq n-1$, $\;i=1,\ldots t$ set % \beqn \theta_n'(v) &=& \frac{\theta_n(v)}{q^{(n-k)/2}},\\ \gamma_{n-1}(i)'(v) &=& \frac{\gamma_{n-1}(i)(v)}{q^{(n+k)/2}}. \eeqn We may check that $\theta_n'$ is an isomorphism of pairs $(V(\Bq(n)),\sqrt{q}\,U_n)$ and $(W(0),U_{n+1})$ that preserves inner products and satisfies \beqn U_{n+1}(v) &=& U_n(v) + q^{(n-k)/2}\;\theta_n'(v),\,\,v\in V(\Bq(n)_k),\;0\leq k \leq n. \eeqn Similarly, it may be checked that $\gamma_{n-1}(i)'$ is an inner product preserving isomorphism of pairs $(V(\Bq(n-1)),\sqrt{q}\,U_{n-1})$ and $(W(i),U_{n+1})$. However, certain computations (notably in the proofs of Theorems \ref{mt3} and \ref{f} below) then become slightly cumbersome due to the presence of many square roots. Therefore we prefer the formulation above where the maps $\theta_n$ and $\gamma_{n-1}(i)$, although they do preserve orthogonality for homogeneous vectors, do not preserve inner products. {{\bf \section { Goldman-Rota recurrence}}} In this section we prove Theorem \ref{grv}. As stated in the introduction, we identify $\Fq^k$, for $k