#  Generalized Gapped-kmer Filters for Robust Frequency Estimation

M. Mohammad-Noori${}^{\textrm{a,c,*}}$, N. Ghareghani${}^{\textrm{b,c}}$, M.
Ghandi${}^{\textrm{d,}}$
${}^{\textrm{a}}$School of Mathematics, Statistics and Computer Science,
College of Science, University of Tehran
P.O. Box 14155-6455, Tehran, Iran
${}^{\textrm{b}}$Department of Engineering Science, College of Engineering,
University of Tehran,
P.O. Box 11165-4563, Tehran, Iran
${}^{\textrm{c}}$School of Mathematics, Institute for Research in Fundamental
Sciences (IPM),
P.O.Box: 19395-5746, Tehran, Iran
${}^{\textrm{d}}$Broad Institute of MIT and Harvard 7 Cambridge Center, 4034C,
Cambridge, MA 02142, United States of America

Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS>Corresponding authors

###### Abstract

In this paper, we study the generalized gapped k-mer filters and derive a
closed form solution for their coefficients. We consider nonnegative integers
$\ell$ and $k$, with $k\leq\ell$, and an $\ell$-tuple
$B=(b_{1},\ldots,b_{\ell})$ of integers $b_{i}\geq 2$, $i=1,\ldots,\ell$. We
introduce and study an incidence matrix $A=A_{\ell,k;B}$. We develop a Möbius-
like function $\nu_{B}$ which helps us to obtain closed forms for a complete
set of mutually orthogonal eigenvectors of $A^{\top}A$ as well as a complete
set of mutually orthogonal eigenvectors of $AA^{\top}$ corresponding to
nonzero eigenvalues. The reduced singular value decomposition of $A$ and
combinatorial interpretations for the nullity and rank of $A$, are among the
consequences of this approach. We then combine the obtained formulas, some
results from linear algebra, and combinatorial identities of elementary
symmetric functions and $\nu_{B}$, to provide the entries of the Moore-Penrose
pseudo-inverse matrix $A^{+}$ and the Gapped k-mer filter matrix $A^{+}A$.

##  1 Introduction

Sequences of length $k$, commonly referred to as $k$-mers, are used in many
computational biology algorithms. We previously showed that robust frequency
estimation of $k$-mers using gapped $k$-mer features could profoundly improve
the performance of algorithms used for sequence classification in
computational biology [7, 6]. The method described in these previous
publications was based on analytically deriving the coefficients of a gapped
$k$-mer filter that could be used to find the robust frequency estimates of
$k$-mers. Although this filter could be applied to datasets consisting of DNA
or Protein sequences, it was not applicable to complex datasets that included
sequences defined on more heterogeneous feature spaces. Here, we provide the
closed-form solution for a generalized gapped $k$-mer filter matrix, by
relaxing the constraint that all the features are defined on a fixed-size
alphabet.

In order to introduce the main object of this introduction, we briefly mention
few definitions and notations here; These are presented in more extent and
details in the body of the paper. Given two integers $\ell$ and $k$ with
$0\leq k\leq\ell$ and a sequence $B=(b_{1},\ldots,b_{\ell})$ of integers
$b_{i}\geq 2$, $i=1,\ldots,\ell$, we associate to them two sets of sequences,
$U_{\ell;B}$ and $V_{\ell,k;B}$, a match relation between the elements of
these two sets and a corresponding $(0,1)$ matrix $A_{\ell,k;B}$ as below. The
set $U_{\ell;B}$ consists of all sequences $x_{1}\cdots x_{\ell}$ of integers
$x_{i}$ satisfying $0\leq x_{i}<b_{i}$ for $i=1,\ldots,\ell$. The set
$V_{\ell,k;B}$ consists of all sequences $y_{1}\cdots y_{\ell}$, where each
$y_{i}$ is either an integer satisfying $0\leq y_{i}<b_{i}$ or an additional
gap symbol denoted as $g$; Furthermore, there are exactly $\ell-k$ occurrences
of the gap symbol in any $y_{1}\cdots y_{\ell}\in V_{\ell,k;B}$. Two sequences
$x_{1}\cdots x_{\ell}\in U_{\ell;B}$ and $y_{1}\cdots y_{\ell}\in
V_{\ell,k;B}$ are then matchable if for any $i$, $1\leq i\leq\ell$, we have
$y_{i}=x_{i}$ or $y_{i}=g$. In other words, the gap symbol $g$ acts as a
wildcard and can match to any symbol. The corresponding $(0,1)$ matrix
$A_{\ell,k;B}$ is then obtained by indexing its columns and rows respectively
by the elements of $U_{\ell;B}$ and $V_{\ell,k;B}$ and setting
$A_{\ell,k;B}(v,u)=1$ if and only if $u$ and $v$ are matchable.

When $b_{1}=\cdots=b_{\ell}=b$, we have a fixed $b$-letter alphabet
$\Sigma_{b}$ and we use the name $A_{\ell,k;b}$ instead of $A_{\ell,k;B}$. In
computational biology for DNA sequences, we have $b=4$, and
$\Sigma_{4}=\\{\texttt{A,C,G,T}\\}$ is the set of four DNA bases. Then the set
of column and row indexes have special names: The set of column indexes,
$\Sigma_{4}^{\ell}$ is non-gapped oligomers of length $\ell$, briefly called
non-gapped $\ell$-mers and the set of row indexes is gapped oligomers with $k$
non-gapped positions and length $\ell$, briefly called gapped $k$-mers (of
length $\ell$). For amino acid sequences, $b=20$, $\Sigma_{20}$ is the set of
the 20 amino acids, and the column indexes and row indexes are the ungapped
and gapped polypeptide sequences of length $\ell$. Apart from some previous
studies of $A_{\ell,k;b}$ in mathematics (see [3, 14, 4]), this matrix has
recently found profound applications in the field of computational biology and
machine learning [7, 6]. Specifically, the inherent symmetry in matrix
$A_{\ell,k;b}$ allowed finding simple closed-form solutions for two related
matrices: $W_{\ell,k;b}$ and $H_{\ell,k;b}$, where
$W_{\ell,k;b}=A_{\ell,k;b}^{+}$ is the Moore-Penrose pseudo-inverse of
$A_{\ell,k;b}$, and $H_{\ell,k;b}$ is the idempotent matrix given by
$H_{\ell,k;b}=W_{\ell,k;b}A_{\ell,k;b}$. In [7] the matrix $W_{\ell,k;b}$ was
derived and used to find robust estimates for $\ell$-mer counts; This led to
significant improvement to predict the binding of certain transcription
factors to DNA sequences. This work was then extended in [6] and the matrix
$H_{\ell,k;b}$ was used to develop a method to efficiently compute the
$\ell$-mer count estimates and to compute a string kernel based on these
robust count estimates to identify enhancer sequences. Beyond modeling
enhancer sequences in mammalian genomes, this method has been widely applied
to several problems in computational biology including prediction of the
effect of non-coding variants [9], identification of local sequence features
influencing cis-regulatory activity [15], identification of accessible
chromatin regions [12], and estimation of evolutionary distances for phylogeny
reconstruction [13].

In all the above applications, the features were defined over a fixed alphabet
length ($b=4$ for DNA/RNA and $b=20$ for amino acids). Here, we show that this
constraint could be relaxed to allow generalizing this method to cases with
mixture of features that are defined over alphabets of different sizes. For
example, in addition to the DNA sequence that is defined over the alphabet
{A,C,G,T}, one can also add DNA methylation status which is defined over
{methylated, unmethylated} alphabet or other discrete features. Then a similar
methodology described in [7] and [6] can be applied to find a robust estimate
of the joint distribution of the features using a limited training data. To
achieve this, we take a similar approach as was used in [7]. We introduce a
Möbius-like function $\nu_{B}$ and use the related identities to obtain
eigenvalues of $A_{\ell,k;B}A_{\ell,k;B}^{\top}$ in terms of elementary
symmetric functions.Then we provide a complete set of mutually orthogonal
eigenvectors of $A_{\ell,k;B}A_{\ell,k;B}^{\top}$ as well as a complete set of
mutually orthogonal eigenvectors of $A_{\ell,k;B}A_{\ell,k;B}^{\top}$
corresponding to the nonzero eigenvalues. This gives the reduced SVD (reduced
singular value decomposition) of $A_{\ell,k;B}$. We also give a combinatorial
interpretations for the nullity and rank of $A_{\ell,k;B}$ via finding
concrete bases for the null space and row space of this matrix. Finally, we
derive an equation for the entries of matrices $W_{\ell,k;B}$ and
$H_{\ell,k;B}$, where $W_{\ell,k;B}=A_{\ell,k;B}^{+}$ is the Moore-Penrose
pseudo-inverse of $A_{\ell,k;B}$ and $H_{\ell,k;B}=W_{\ell,k;B}A_{\ell,k;B}$.
Deriving an explicit formula for matrices $A_{\ell,k;B}$ and $H_{\ell,k;B}$
allows efficient computation of robust count estimates from a given training
data. In practice, even with modest values of $\ell$ and $k$, these matrices
have exponentially large dimensions which makes the application of numeric
methods unfeasible.

The rest of the paper is organized as following: Introduction of notation and
preliminaries is given in Section 2: General notations and definitions for
sets, strings, sequences, relations and some symmetric polynomials are
presented in Section 2.1; Some preliminaries from linear algebra are discussed
in Section 2.2. The function $\nu_{B}$ and some of its properties is defined
and studied in Section 3; The main results of this section, that is the
identities given in Propositions 1, 2 and 3, are used in later sections. Using
the definition of function $\nu_{B}$ and also the elementary symmetric
polynomials, we propose an orthonormal basis for the eigenspaces of the matrix
$A_{\ell,k;B}A_{\ell,k;B}^{\top}$ in Section 4. Concrete bases for the null
space and the row space of $A_{\ell,k;B}$ are presented in Section 5. Finally,
in Section 6 we compute the entries of $W_{\ell,k;B}$ and $H_{\ell,k;B}$.

##  2 Notation and Preliminaries

###  2.1 Notation for sets, strings, sequences and relations

###### Definition 1

. Let $\ell$ be a positive integer. The set $[\ell]$ is defined as
$[\ell]=\\{1,\ldots,\ell\\}$. For a set $X$ and a nonnegative integer $n$, by
${X\choose n}$, we mean the set of all $n$-element subsets of $X$. Thus
$|{X\choose n}|={|X|\choose n}$ and $|{[\ell]\choose n}|={\ell\choose n}$.

###### Definition 2

. A word $x$ on a finite alphabet $\Sigma$, is a sequence $x=x_{1}\cdots
x_{\ell}$ whose elements $x_{i}$ belong to the set $\Sigma$. As in [7] for a
given integer $b\geq 2$, the sets $\Sigma_{b}$, $\Delta_{b}$, $\Gamma_{b}$ are
defined as follows

$\Sigma_{b}=\\{0,1,\cdots,b-1\\},\,\,\,\,\Delta_{b}=\Sigma_{b}\cup\\{g\\},\,\,\,\,\Gamma_{b}=\Delta_{b}\setminus\\{0\\},$

where $g$ stands for the gap symbol.

###### Definition 3

. Let $B=(b_{1},b_{2},\ldots,b_{\ell})$ be an $\ell$-tuple of integers
$b_{i}\geq 2$. Define the sets $\Sigma_{B}$, $\Delta_{B}$, $\Gamma_{B}$,
$U_{\ell;B}$ and $V_{\ell,k;B}$ as follows

$\displaystyle\Sigma_{B}$
$\displaystyle=\Sigma_{b_{1}}\times\cdots\times\Sigma_{b_{\ell}},\,\,\Delta_{B}=\Delta_{b_{1}}\times\cdots\times\Delta_{b_{\ell}},$
$\displaystyle\Gamma_{B}$
$\displaystyle=\Gamma_{b_{1}}\times\cdots\times\Gamma_{b_{\ell}},\,\,U_{\ell;B}=\Sigma_{B},$
$\displaystyle V_{\ell,k;B}$
$\displaystyle=\\{v\in\Delta_{B}:|v|_{g}=\ell-k\\},\,\,V^{\prime}_{\ell,k;B}=\\{w\in\Gamma_{B}:|w|_{g}=\ell-k\\},$
$\displaystyle V_{\ell,\leq k;B}$ $\displaystyle=\bigcup_{m=0}^{k}V_{\ell
m},\,\,V^{\prime}_{\ell,\leq k;B}=\bigcup_{m=0}^{k}V^{\prime}_{\ell m}$

A weak partial order on a set $S$ is a binary relation $\preceq$ on $S$ which
is reflexive, transitive and antisymmetric. A set equipped with a weak partial
order is called a partially ordered set or briefly a poset. If $a\preceq b$
and $a\neq b$ we write $a\prec b$; Then $\prec$ is nonreflexive, transitive
and nonsymmetric; Such a relation is called a strong partial order on $S$. If
$\preceq_{1}$ (resp. $\preceq_{2}$ ) is a weak partial order on $S$ (resp.
$T$), then $\preceq_{1}\times\preceq_{2}$ is a weak partial order on $S\times
T$. If for any $a$ and $b$ in $S$, either $a\prec b$ or $b\prec a$, then the
partial order is called a total order, or a linear order. This notation is
used in the following definition.

###### Definition 4

. Let $B=(b_{1},b_{2},\ldots,b_{\ell})$. We define a partial order on the set
$\Delta_{B}$. For this purpose, firstly for any $1\leq i\leq\ell$, we consider
the order $\prec_{i}$ on the set $\Delta_{b_{i}}$ given by

$0\prec_{i}1\prec_{i}\ldots\prec_{i}b_{i}-1\prec_{i}g$

and consider the order
$\preceq_{B}\,:=\,(\preceq_{1}\times\ldots\times\preceq_{\ell})$ on
$\Delta_{B}$.

###### Remark 1

. As it is clear from the definitions of $U_{\ell;B}$ and $V_{\ell,k;B}$, when
we use these notations we specially emphasize on parameters $\ell$ and $k$.

###### Definition 5

. For any word $v\in\Delta_{B}$ we set $G_{v}=\\{i:1\leq i\leq\ell,v_{i}=g\\}$
and $\overline{G}_{v}=[\ell]\setminus G_{v}$. If $X=\\{x_{1},\cdots,x_{n}\\}$
is a subset of $\\{1,\cdots,\ell\\}$ with $x_{1}<x_{2}<\ldots<x_{n}$ then by
$B(X)$ we mean $(b_{x_{1}},\ldots,b_{x_{n}})$. Especially, if $v\in\Delta_{B}$
and $v^{\prime}\in\Gamma_{B}$, then $B(G_{v})=(b_{i})_{i\in G_{v}}$ and
$B(G_{v^{\prime}})=(b_{i})_{i\in G_{v^{\prime}}}$.

###### Definition 6

. Let $B=(b_{1},\ldots,b_{\ell})$. We say elements $u\in\Sigma_{B}$ and
$v\in\Delta_{B}$ match (or $u$ and $v$ are matchable) if for any $1\leq
i\leq\ell$ with $v_{i}\neq g$ we have $u_{i}=v_{i}$; We denote this by $v\sim
u$. The set of the elements $v\in V_{\ell,k;B}$ which are matchable with
$u\in\Sigma_{B}$, is denoted by $M_{\ell,k;B}(u)$. The set of elements
$u\in\Sigma_{B}$ which are matchable with $v$, is denoted by
$N_{\ell,k;B}(v)$.

###### Definition 7

. The matrix $A_{\ell,k;B}$ is defined as a $(0,1)$ matrix whose rows and
columns are indexed respectively by the elements of $V_{\ell,k;B}$ and
$\Sigma_{B}$ and $A_{\ell,k;B}(v,u)=1$ if and only if $u$ and $v$ are
matchable.

###### Remark 2

. Considering the definition 7, if we identify each row index $v\in
V_{\ell,k;B}$ with $N_{\ell,k;B}(v)$, then the matrix $A_{\ell,k;B}$ is seen
as an incidence matrix, in which the points and blocks are row indexes and
column indexes, respectively.

###### Definition 8

. The matrix $A_{\ell,\leq k;B}$ is defined as the $(0,1)$ matrix obtained by
stacking the matrices $A_{\ell,i;B}$ ($i=0,\ldots,k$), one on top of the
other; Thus the rows and columns of $A_{\ell,\leq k;B}$ are indexed
respectively by the elements of $V_{\ell,\leq k;B}$ and $U_{\ell,B}$.

Elementary symmetric polynomials are well-studied objects in the study of
polynomials ring $k[x_{1},x_{2},\ldots,x_{n}]$ (see Chapter $7$ of [2]). Below
we formally mention their definitions; Then we define another symmetric
polynomial which is useful in our work. This is followed by an example
demonstrating their applications in our work.

###### Definition 9

. Let $i$ and $n$ be nonnegative integers and let
$X=(x_{1},x_{2},\ldots,x_{n})$ be a finite sequence of variables. The $i$-th
elementary symmetric polynomial, denoted as $S_{i}(X)$, is defined as
$S_{i}(X):=\sum_{I\in{X\choose i}}\prod_{i\in I}x_{i}$.

Notation. Let $X=(x_{1},\ldots,x_{n})$ be a finite sequence of numbers and
$\alpha$ and $\beta$ be arbitrary numbers. Then we show the sequence $(\beta
x_{1}+\alpha,\ldots,\beta x_{n}+\alpha)$ by $\beta X+\alpha$.

###### Definition 10

. Let $i$ and $n$ be nonnegative integers and let
$X=(x_{1},x_{2},\ldots,x_{n})$ be a finite sequence of variables. The
expression $R_{i}(X)$ is then defined as follows:

$R_{i}(X)=\sum_{j=0}^{i}S_{j}(X-1)$ (1)

###### Example 1

. Let $0\leq k\leq\ell$ be integers and $B=(b_{1},\ldots,b_{\ell})$,
$u\in\Sigma_{B}$ and $v\in V_{\ell k;B}$. Then we have

$\displaystyle|\Sigma_{B}|=|\Gamma_{B}|=\prod_{i=1}^{\ell}b_{i},\,\,\,$
$\displaystyle|V_{\ell,k;B}|=S_{k}(B),\,\,\,\ $
$\displaystyle|V^{\prime}_{\ell,k;B}|=S_{k}(B-1),\,\,\,$
$\displaystyle|V_{\ell,\leq k;B}|=R_{k}(B+1),$
$\displaystyle|V^{\prime}_{\ell,\leq k;B}|=R_{k}(B),\,\,\,$
$\displaystyle|M_{\ell,k}(u)|={\ell\choose k},\,\,\,$
$\displaystyle|N_{\ell,k}(v)|=\prod_{i\in G_{v}}b_{i},\,\,\,$

###  2.2 Notation and preliminaries from Linear Algebra

All matrices we concern in this paper are real matrices. The row space of a
$A$ is denoted as ${\rm row}(A)$, the column space of $A$ is denoted as ${\rm
col}(A)$, and the dimension of the row space of $A$ is denoted as ${\rm
rank}(A)$. The kernel of $A$, denoted as ${\ker}(A)$ and the nullity of $A$
and denoted as ${\rm null}(A)$. The matrix $A$ is called diagonalizable in the
field of real numbers if there exists a nonsingular real matrix $P$ such that
$A=P\Lambda_{0}P^{-1}$ for some diagonal real matrix $\Lambda_{0}$. If $A$ is
diagonalizable, then all eigenvalues of $A$ appear on the main diagonal of
$\Lambda_{0}$ and the columns of $P$ are the corresponding eigenvectors. The
set of column vectors of $P$ is called a complete set of eigenvectors of $A$;
The set of column vectors of $P$ which correspond to nonzero eigenvalues is
called a complete set of nonzero eigenvectors of $A$. If eigenvectors
belonging to distinct eigenvalues of the matrix $A$ are mutually orthogonal,
then there exists an eigendecomposition $A=P\Lambda_{0}P^{-1}$ with
$P^{-1}=P^{\top}$, we call such a decomposition an orthogonal
eigendecomposition. Let $A=P\Lambda_{0}P^{\top}$ be a orthogonal
eigendecomposition for the matrix $A$ and $P=[Q\,N]$ where ${\rm
col}(N)={\ker}(A)$. Then $A=Q\Lambda Q^{\top}$, where the matrix $Q$ is
obtained by deleting the columns of $P$ which are in ${\ker}(A)$, and
$\Lambda$ is obtained by deleting the zero columns and zero rows of
$\Lambda_{0}$; we call this decomposition an orthonormal nonzero
eigendecomposition.

It is known that any symmetric real matrix $A$ is diagonalizable on the field
of real numbers and eigenvectors corresponding to distinct eigenvalues of $A$
are orthogonal. Hence, every symmetric real matrix $A$ has an orthonormal
nonzero eigendecomposition of the form $A=Q\Lambda Q^{\top}$ with real
matrices $\Lambda$ and $Q$. A real symmetric matrix $A$ of order $n$ is
positive definite (resp. positive semi-definite) if ${\bf x}^{\top}A{\bf x}>0$
(resp. ${\bf x}^{\top}A{\bf x}\geq 0$) for all nonzero ${\bf
x}\in\mathbb{R}^{n}$. For any matrix $A$, the matrix $A^{\top}A$ is positive
semidefinite, and ${\rm rank}(A)={\rm rank}(AA^{\top})$. Conversely, any
positive semidefinite matrix $M$ can be written as $M=A^{\top}A$; this is the
Cholesky decomposition. If $A$ is a real matrix, then both $A^{\top}A$ and
$AA^{\top}$ are diagonalizable over the field of real numbers.

A singular value decomposition (SVD) of a matrix $A\in{\mathbb{R}}^{n\times
m}$ is a factorization $A=U\Sigma V^{\top}$ with $\Sigma={\rm
diag}(\sigma_{1},\sigma_{2},\ldots,\sigma_{p})$, $p=\min\\{n,m\\}$ and
$\sigma_{1}\geq\sigma_{2}\geq\ldots\geq\sigma_{p}\geq 0,$ such that the set of
columns of both matrices $U=[{\bf u_{1}},{\bf u_{2}},\ldots,{\bf
u_{n}}]\in{\mathbb{R}}^{n\times n}$ and $V=[{\bf v_{1}},{\bf
v_{2}},\ldots,{\bf v_{m}}]\in{\mathbb{R}}^{m\times m}$ are orthonormal. The
diagonal entries of $\Sigma$ are called singular values of $A$. If ${\rm
rank}(A)=r<p$, then the reduced singular value decomposition (reduced SVD) of
$A$ is a factorization $A={\hat{U}}{\hat{\Sigma}}{\hat{V}}^{\top}$ with
${\hat{\Sigma}}={\rm
diag}(\sigma_{1},\sigma_{2},\ldots,\sigma_{r})\in{\mathbb{R}}^{r\times r}$ and
$\sigma_{1}\geq\sigma_{2}\geq\ldots\geq\sigma_{r}>0$, such that the matrices
$U=[{\bf u_{1}},{\bf u_{2}},\ldots,{\bf u_{r}}]\in{\mathbb{R}}^{n\times r}$
and $V=[{\bf v_{1}},{\bf v_{2}},\ldots,{\bf v_{r}}]\in{\mathbb{R}}^{m\times
r}$ are both orthonormal. The following lemma gives the relation between the
SVD of matrix $A$ and eigendecomposition of the matrices $AA^{\top}$ and
$A^{\top}A$.

###### Lemma 1

.([5], Section 5.6, Facts 8,9) Let $A\in{\mathbb{R}}^{n\times m}$, then the
following facts holds:

  * (i)

The nonzero singular values of $A$ are the square roots of nonzero eigenvalues
of $A^{\top}A$ or $AA^{\top}$.

  * (ii)

if ${{U}}{{\Sigma}}{{V}}^{\top}$ is a reduced SVD of $A$, then columns of
${V}$ are eigenvectors of $A^{\top}A$ and columns of ${U}$ are eigenvectors of
$AA^{\top}$.

The Moore-Penrose pseudo-inverse of a matrix $A$, denoted by $A^{+}$, is
defined as a matrix that satisfies all the following four conditions:

$AA^{+}A=A,\,\,\,\,\,A^{+}AA^{+}=A^{+},\,\,\,\,\,(AA^{+})^{{}^{\top}}=AA^{+},\,\,\,\,\,(A^{+}A)^{{}^{\top}}=A^{+}A$

The Moore-Penrose pseudo-inverse exists and is unique for any given matrix
$A$. We have $A^{+}=(A^{\top}A)^{+}A^{\top}=A^{\top}(AA^{\top})^{+}$. For
further properties of the Moore-Penrose pseudo-inverse see for instance [5].
The two following Lemmas provide the Moore-Penrose pseudo-inverse of the
matrix $A$ based on some nonzero eigendecomposition of $AA^{\top}$. The proof
of the first one is straight forward and left to the readers.

The following lemmas provide the Moore-Penrose pseudo-inverse of a matrix $A$
based on some nonzero eigendecomposition of the matrix $AA^{\top}$.

###### Lemma 2

. Let $B$ be a positive semi-definite real matrix. Then $B$ admits an
orthonormal nonzero eigendecomposition of the form $B=Q\Lambda Q^{\top}$.
Where $Q^{\top}Q=I$. Moreover let $B=AA^{\top}$, then we have
$A^{\top}QQ^{\top}=A^{\top}$.

###### Proof.

Using the previous notation, let $AA^{\top}=P\Lambda_{0}P^{\top}$ be an
orthonormal decomposition for $AA^{\top}$ and $P=[Q\,N]$ where the columns of
$N$ are in ${\ker}(AA^{\top})$. The equation $Q^{\top}Q=I$ is concluded from
the orthonormality of the columns of $Q$. If ${\bf y}$ denotes a column of
$N$, by $A_{\ell k}A_{\ell k}^{\top}{\bf y}=0$ we obtain ${\bf
y}^{\top}A_{\ell k}A_{\ell k}^{\top}{\bf y}=0$, hence $||A_{\ell k}^{\top}{\bf
y}||=0$, which yields $A_{\ell k}^{\top}{\bf y}=0$. Thus $A^{\top}N=0.$ Now,
from $PP^{\top}=I$ we obtain $QQ^{\top}+NN^{\top}=I$; Multiplying from left by
$A^{\top}$ and using $A^{\top}N=0$, we provide $A^{\top}QQ^{\top}=A^{\top}$.
$\Box$

###### Lemma 3

. Let $A_{n\times m}$ be a real matrix and let $AA^{\top}=Q\Lambda Q^{\top}$
be a nonzero orthonormal eigendecomposition of $AA^{\top}$. Then the Moore-
Penrose pseudo-inverse of $A$ is given by $W=A^{\top}Q\Lambda^{-1}Q^{\top}$.
Moreover, if the all one column vector ${\bf j}=[1\,1\,\ldots 1]^{\top}$ is an
eigenvector of $A^{\top}A$, then $WA{\bf j}={\bf j}$.

###### Proof.

The proof is easily obtained by using Lemma 2. $\Box$

###### Lemma 4

. Let $A_{n\times m}$ be a real matrix and suppose that the columns of
$\Upsilon$ are a complete set of eigenvectors corresponding to nonzero
eigenvalues of $AA^{\top}$. Let the columns of $\Upsilon$ be
$c_{1},\ldots,c_{n}$ corresponding to the nonzero eigenvalues
$\lambda_{1},\ldots,\lambda_{n}$.

  * (i)

An orthonormal nonzero eigendecomposition $AA^{\top}=Q\Lambda Q^{\top}$ is
obtained by setting $Q=\Upsilon E$, where $E={\rm
diag}(\frac{1}{\|c_{i}\|})_{1\leq i\leq n}$.

  * (ii)

If we denote Moore-Penrose pseudo-inverse of $A$ by $W$, then
$W=A^{\top}\Upsilon D\Upsilon^{\top}$, where $D={\rm
diag}(\frac{1}{||c_{i}||^{2}\lambda_{i}})_{1\leq i\leq n}$. Consequently,
$W=A^{\top}C$ where the entries of $C$ are given by
$C_{ij}=\sum_{k}\frac{\Upsilon_{ik}\Upsilon_{jk}}{||c_{k}||^{2}\lambda_{k}}$.

###### Proof.

  * (i)

In order to obtain normal eigenvectors, it is enough to divide column $c_{i}$
of $\Upsilon$ by its norm, that is to multiply the matrix $\Upsilon$ from
right by the diagonal matrix $E={\rm diag}(\frac{1}{||c_{i}||})_{1\leq i\leq
n}$ to get $Q=\Upsilon E$.

  * (ii)

By Lemma 3, $W=A^{\top}Q\Lambda^{-1}Q^{\top}=A^{\top}\Upsilon
E\Lambda^{-1}E^{\top}\Upsilon^{\top}$. Since both $E$ and $\Lambda$ are
diagonal, so is $E\Lambda^{-1}E^{\top}$; Setting $D=E\Lambda^{-1}E^{\top}$, we
obtain $W=A^{\top}\Upsilon D\Upsilon^{\top}$, where $D={\rm
diag}(\frac{1}{||c_{i}||^{2}\lambda_{i}})_{1\leq i\leq n}$; Setting
$C=\Upsilon D\Upsilon^{\top}$ we obtain $W=A^{\top}C$ and
$C_{ij}=\sum_{k}\frac{\Upsilon_{ik}\Upsilon_{jk}}{||c_{k}||^{2}\lambda_{k}}$,
as required.

$\Box$

##  3 The function $\nu_{B}$ and some of its properties

In this section, we consider an order on the set $\Delta_{B}$ and based on
this define a function $\nu_{B}$ on the set $\Delta_{B}\times\Delta_{B}$ and
inspect some of its properties. For an integer $b_{i}\geq 2$, the following
linear order makes $\Delta_{b_{i}}$ a totally ordered set:

$0\prec_{i}1\prec_{i}\ldots\prec_{i}b_{i}-1\prec_{i}g$

and when this order is induced on the product set
$\Delta_{B}=\Delta_{b_{1}}\times\cdots\times\Delta_{b_{\ell}}$, a poset is
obtained; More precisely, for two elements $x=x_{1}\cdots x_{\ell}$ and
$y=y_{1}\cdots y_{\ell}$ with $x_{i},y_{i}\in\Delta_{b_{i}}$, $(1\leq
i\leq\ell)$, we have $x\preceq_{B}y$ if and only if $x_{i}\preceq_{i}y_{i}$
holds for $i=1,\ldots,\ell$. Below is presented the definition of a useful
function on $\Delta_{B}\times\Delta_{B}$.

###### Definition 11

. Consider the $\ell$-tuple $B=(b_{1},b_{2},\ldots,b_{\ell})$, where
$b_{i}\geq 2$ is integer for $i=1,\ldots,\ell$. For any $i$, $(1\leq
i\leq\ell)$, we define the function $\nu_{i}$ on
$\Delta_{b_{i}}\times\Delta_{b_{i}}$ as

$\nu_{i}(x,y)=\left\\{\begin{matrix}-b_{i}&\text{if }\,\,x=y=g,\\\ -y&\text{if
}x=y\neq g,\\\ 1&\text{if }\,\,x\prec y,\\\ 0&\text{if }x\succ
y.\end{matrix}\right.$

Now the function $\nu_{B}$ is defined on the product set
$\Delta_{B}\times\Delta_{B}$ by the following product rule

$\nu_{B}(x_{1}\cdots x_{\ell},y_{1}\cdots
y_{\ell})=\prod_{i=1}^{\ell}\nu_{i}(x_{i},y_{i})$ (2)

###### Remark 3

. The function $\nu$ satisfies the property “ $\nu_{B}(x,y)=0$ unless
$x\preceq_{B}y$”; This means that it is an element of the incidence algebra of
the poset $\Delta_{B}$ (For the definition and some examples of this concept,
see for instance Chapter 8 of [1]). It is observed that $\nu_{B}$ satisfies

$\sum_{x\preceq z\preceq
y}\nu_{B}(x,z)=\left\\{\begin{matrix}\prod_{i=1}^{\ell}(y^{\prime}_{i}-2x^{\prime}_{i})&\text{if
}\,\,x\preceq y,\\\ 0&\text{otherwise. }\end{matrix}\right.$ (3)

where the values $x^{\prime}_{i}$, $(1\leq i\leq\ell),$ are defined

$x^{\prime}_{i}=\left\\{\begin{matrix}b_{i}&\text{if }\,\,x_{i}=g,\\\
x_{i}&\text{otherwise. }\end{matrix}\right.$

and $y^{\prime}_{i}$’s are defined similarly. The equation (3) shows
similarities between the function $\nu_{B}$ and the Möbius function of the
poset $\Delta_{B}$.

Some useful identities about $\nu_{B}$ are stated in Proposition 1, but before
stating this proposition we need some definitions and lemmas.

###### Definition 12

. Let $\ell$ be a positive integer, $B=(b_{1},\ldots,b_{\ell})$ and let
$v^{\prime},v^{\prime\prime}\in\Delta_{B}$. Let $m,n$ be integers with $0\leq
m,n\leq\ell$ such that $|G_{v^{\prime}}|=\ell-n$ and
$|G_{v^{\prime\prime}}|=\ell-m$. Define the sets $A_{3},A_{2},A_{1}$ and
$A_{0}$ by
$A_{3}=\overline{G}_{v^{\prime}}\cap\overline{G}_{v^{\prime\prime}}$,
$A_{2}=G_{v^{\prime\prime}}\setminus G_{v^{\prime}}$,
$A_{1}=G_{v^{\prime}}\setminus G_{v^{\prime\prime}}$ and
$A_{0}=G_{v^{\prime}}\cap G_{v^{\prime\prime}}$.

###### Lemma 5

. Let $v^{\prime},v^{\prime\prime}\in\Delta_{B}$ and the sets $A_{0}$,
$A_{1}$,$A_{2}$ and $A_{3}$ be as in Definition 12.

  * (i)

The sets $A_{3},A_{2},A_{1}$ and $A_{0}$ are mutually disjoint and $A_{0}\cup
A_{1}\cup A_{2}\cup A_{3}=[\ell]$. Moreover $A_{0}\neq[\ell]$ unless
$v^{\prime}=v^{\prime\prime}=g^{\ell}$.

  * (ii)

If $A_{1}=A_{2}=\emptyset$, then $A_{0}=G_{v}=G_{v^{\prime}}$ and
$\overline{G}_{v^{\prime}}=\overline{G}_{v^{\prime\prime}}=A_{3}$; If
furthermore $v^{\prime}\neq v^{\prime\prime}$, then there exists $i\in A_{3}$
such that $v^{\prime}_{i}\neq v^{\prime\prime}_{i}$

###### Proof.

The proof is straightforward.  $\Box$

###### Lemma 6

. Let $w,v^{\prime},v^{\prime\prime}\in\Delta_{B}$.

  * (i)

If $\nu_{B}(w,v^{\prime})\nu_{B}(w,v^{\prime\prime})\neq 0$, then
$G_{w}\subseteq A_{0}$.

  * (ii)

If $G_{w}\subseteq A_{0}$, then
$\nu_{B}(w,v^{\prime})\nu_{B}(w,v^{\prime\prime})=p_{3}p_{2}p_{1}p_{0}$, where

$\displaystyle p_{0}=$ $\displaystyle\prod_{i\in G_{w}}b_{i}^{2},$
$\displaystyle p_{1}=\prod_{i\in A_{1}}{\nu}_{i}(w_{i},v^{\prime\prime}_{i}),$
$\displaystyle p_{2}=$ $\displaystyle\prod_{i\in
A_{2}}{\nu}_{i}(w_{i},v^{\prime}_{i}),$ $\displaystyle p_{3}=\prod_{i\in
A_{3}}{\nu}_{i}(w_{i},v^{\prime}_{i}){\nu}_{i}(w_{i},v^{\prime\prime}_{i})$

###### Proof.

The proof of part (i) is straightforward. The proof of part (ii) is obtained
using

$\displaystyle\nu_{B}(w,v^{\prime})\nu_{B}(w,v^{\prime\prime})=$
$\displaystyle\prod_{i=1}^{\ell}{\nu}_{i}(w_{i},v^{\prime}_{i}){\nu}_{i}(w_{i},v^{\prime\prime}_{i})$
$\displaystyle=$ $\displaystyle\prod_{j=0}^{3}\prod_{i\in
A_{j}}{\nu}_{i}(w_{i},v^{\prime}_{i}){\nu}_{i}(w_{i},v^{\prime\prime}_{i}),$

and the definition of $\nu_{i}$.  $\Box$

###### Proposition 1

. Let $v^{\prime},v^{\prime\prime}\in\Gamma_{B}$. Then

  * (i)

${\displaystyle\sum_{w\in V_{\ell
k}}\nu_{B}(w,v^{\prime})=\left\\{\begin{array}[]{rl}(-1)^{\ell-k}S_{\ell-k}(B),&\hbox{if
$v^{\prime}=g^{\ell}$,}\\\ \\\ 0,&\hbox{otherwise. }\end{array}\right.}$

  * (ii)

${\displaystyle\sum_{w\in V_{\ell
k}}\nu_{B}(w,v^{\prime})\nu_{B}(w,v^{\prime\prime})=\left\\{\begin{array}[]{rl}{\displaystyle
S_{\ell-k}(B(G_{v^{\prime}}))\prod_{i\in
G_{v^{\prime}}}b_{i}\prod_{i\in\overline{G}_{v^{\prime}}}(v^{\prime}_{i}+{v^{\prime}_{i}}^{2})},&\hbox{if
$v^{\prime}=v^{\prime\prime}$,}\\\ \\\ 0,&\hbox{otherwise.
}\end{array}\right.}$

###### Proof.

  * (i)

For $w\in V_{\ell,k}$ we have $\nu_{B}(w,g^{\ell})=\prod_{i\in
G_{w}}(-b_{i})$, hence we obtain

$\displaystyle\sum_{w\in V_{\ell
k}}\nu_{B}(w,g^{\ell})=(-1)^{\ell-k}S_{\ell-k}(B)$

which proves part(i) in the case $v^{\prime}=g^{\ell}$.

Now suppose that $v^{\prime}\in V_{\ell;\leq k;B}\setminus\\{g^{\ell}\\}$,
hence for some $1\leq j\leq\ell$, $v^{\prime}_{j}\neq g$. Then from

$\displaystyle{\displaystyle\sum_{w\in V_{\ell k}}\nu_{B}(w,v^{\prime})}=$
$\displaystyle\sum_{w_{i}=0}^{b_{i}-1}\prod_{i=1}^{\ell}\nu_{i}(w_{i},v^{\prime}_{i})$
$\displaystyle=$
$\displaystyle\prod_{i=1}^{\ell}\sum_{w_{i}=0}^{b_{i}-1}\nu_{i}(w_{i},v^{\prime}_{i}),$

by using $\sum_{w_{j}=0}^{b_{j}-1}\nu_{j}(w_{j},v^{\prime}_{j})=0$, the right
side is simplified to $0$, as required.

  * (ii)

To prove this part, observe that if $|A_{0}|<\ell-k$, each summand in the
left, is zero and there is nothing to prove. So, let $|A_{0}|\geq\ell-k$;
Setting $X_{\ell k}(B,G)=\\{w\in V_{\ell k}(B):G_{w}=G\\}$ we obtain

$\sum_{w\in V_{\ell
k}(B)}\nu_{B}(w,v^{\prime})\nu_{B}(w,v^{\prime\prime})=\sum_{G\in{{A_{0}}\choose{\ell-k}}}\sum_{w\in
X_{\ell k}(B,G)}\nu_{B}(w,v^{\prime})\nu_{B}(w,v^{\prime\prime})$ (4)

First we compute the summand $\sum_{w\in X_{\ell
k}(B,G)}\nu(w,v^{\prime})\nu(w,v^{\prime\prime})$, for a fixed
$G\in{{A_{0}}\choose{\ell-k}}$. For this, without loss of generality, let
$A_{3}=\\{1,\ldots,a_{3}\\}$, $A_{2}=\\{a_{3}+1,\ldots,a_{3}+a_{2}\\}$,
$A_{1}=\\{a_{3}+a_{2}+1,\ldots,a_{3}+a_{2}+a_{1}\\}$ and
$A_{0}=\\{a_{3}+a_{2}+a_{1}+1,\ldots,\ell\\}$, where $a_{1},a_{2},a_{3}$ are
non-negative integers. Moreover, without loss of generality, let
$G=\\{k+1,\ldots,\ell\\}$. Now $w\in X_{\ell k}(B,G)$ can be factorized in the
form $w=qrstg^{\ell-k}$, with $|q|=a_{3}$, $|r|=a_{2}$, $|s|=a_{1}$ and
$|t|=a_{0}-(\ell-k)$ and when $w$ runs over $X_{\ell k}(B,G)$, each of the
words $q,r,s$ and $t$ runs over a proper set accordingly. By part (ii) of
Lemma 6 we obtain

$\sum_{w\in X_{\ell
k}(B,G)}\nu_{B}(w,v^{\prime})\nu_{B}(w,v^{\prime\prime})=P_{3}P_{2}P_{1}P_{0},$
(5)

where

$\displaystyle P_{0}=$ $\displaystyle\prod_{i\in A_{0}}b_{i}\prod_{i\in
G}b_{i},$ $\displaystyle P_{1}=\prod_{i\in
A_{1}}\sum_{w_{i}=0}^{b_{i}-1}{\nu}_{i}(w_{i},v^{\prime}_{i}),$ $\displaystyle
P_{2}=$ $\displaystyle\prod_{i\in
A_{2}}\sum_{w_{i}=0}^{b_{i}-1}{\nu}_{i}(w_{i},v^{\prime\prime}_{i}),$
$\displaystyle P_{3}=\prod_{i\in
A_{3}}\sum_{w_{i}=0}^{b_{i}-1}{\nu}_{i}(w_{i},v^{\prime}_{i}){\nu}_{i}(w_{i},v^{\prime\prime}_{i})$

Now, we consider two cases:
Case 1. $v^{\prime}=v^{\prime\prime}$; In this case $A_{0}=G_{v^{\prime}}$ and
$A_{1}=A_{2}=\emptyset$, hence $P_{1}=P_{2}=1$ and $\sum_{w\in X_{\ell
k}(B,G)}\nu_{B}^{2}(w,v^{\prime})=P_{3}P_{0}$. In this case,
$P_{3}={\displaystyle\prod_{i\in{\overline{G}}_{v^{\prime}}}(v^{\prime}_{i}+{v^{\prime}_{i}}^{2})}$
and $P_{0}={\displaystyle\prod_{i\in G_{v^{\prime}}}b_{i}\prod_{i\in
G}b_{i}}$, so

$\displaystyle\sum_{w\in V_{\ell
k}(B)}\nu_{B}(w,v^{\prime})\nu_{B}(w,v^{\prime\prime})=$
$\displaystyle\sum_{G\in{{G_{v^{\prime}}}\choose{\ell-k}}}\sum_{w\in X_{\ell
k}(B,G)}\nu_{B}(w,v^{\prime})\nu_{B}(w,v^{\prime\prime})$ $\displaystyle=$
$\displaystyle\sum_{G\in{{G_{v^{\prime}}}\choose{\ell-k}}}\prod_{i\in{\overline{G}}_{v^{\prime}}}(v^{\prime}_{i}+{v^{\prime}_{i}}^{2})\prod_{i\in
G_{v^{\prime}}}b_{i}\prod_{i\in G}b_{i}$ $\displaystyle=$
$\displaystyle\prod_{i\in{\overline{G}}_{v^{\prime}}}(v^{\prime}_{i}+{v^{\prime}_{i}}^{2})\prod_{i\in
G_{v^{\prime}}}b_{i}\sum_{G\in{{A_{0}}\choose{\ell-k}}}\prod_{i\in G}b_{i}$
$\displaystyle=$
$\displaystyle\prod_{i\in{\overline{G}}_{v^{\prime}}}(v^{\prime}_{i}+{v^{\prime}_{i}}^{2})\prod_{i\in
G_{v^{\prime}}}b_{i}\,\,\,\,\,S_{\ell-k}(B(G_{v^{\prime}}))$

Case 2. $v^{\prime}\neq v^{\prime\prime}$; If $A_{1}\neq\emptyset$ then
$P_{1}=0$ and if $A_{2}\neq\emptyset$ then $P_{2}=0$. Otherwise, if
$A_{1}=A_{2}=\emptyset$, then by Lemma 5 (ii), $A_{3}\neq\emptyset$ and there
exists $i\in A_{3}$ with $v^{\prime}_{i}\neq v^{\prime\prime}_{i}$; For this
$i$,
$\sum_{w_{i}}\nu_{i}(w_{i},v^{\prime}_{i})\nu_{i}(w_{i},v^{\prime\prime}_{i})=0$
thus $P_{3}=0$. Hence, the hypothesis $v^{\prime}\neq v^{\prime\prime}$
implies that the right side of (5) is zero in either case, and we get the
result by (4).

$\Box$

###### Proposition 2

. Let $v^{\prime}\in\Gamma_{B}$. Then

  * (i)

For any $u\in U_{\ell}$ we have

$\sum_{y\in
M_{\ell,k;B}(u)}\nu_{B}(y,v^{\prime})=(-1)^{\ell-k}S_{\ell-k}(B(G_{v^{\prime}}))\,\nu_{B}(u,v^{\prime}),$
(6)

  * (ii)

For any $v\in V_{\ell k}$ we have

$\sum_{u\in
N_{\ell,k;B}(v)}\nu_{B}(u,v^{\prime})=(-1)^{\ell-k}\nu_{B}(v,v^{\prime})$ (7)

###### Proof.

  * (i)

If the summand $\nu(y,v^{\prime})$ is nonzero, then $G_{y}\subseteq
G_{v^{\prime}}$, on the other hand the non-gaped positions of all such $y$’s
are the same as $u$. Let $G_{y}=\\{x_{1},x_{2},\ldots,x_{\ell-k}\\}$, then
$\nu_{B}(y,v^{\prime})=(-1)^{\ell-k}b_{x_{1}}b_{x_{2}}\cdots
b_{x_{\ell-k}}\,\nu_{B}(u,v^{\prime})$. Therefore

$\displaystyle\sum_{y\in M_{\ell,k;B}(u)}\nu_{B}(y,v^{\prime})=$
$\displaystyle(-1)^{\ell-k}\nu_{B}(u,v^{\prime})\sum_{\\{x_{1},x_{2},\ldots,x_{\ell-k}\\}\subseteq
G_{v^{\prime}}}b_{x_{1}}b_{x_{2}}\ldots b_{x_{\ell-k}}$ $\displaystyle=$
$\displaystyle(-1)^{\ell-k}S_{\ell-k}(B(G_{v^{\prime}}))\,\nu_{B}(u,v^{\prime}),$

as required.

  * (ii)

We distinguish two cases:

Case (a). Suppose that $G_{v}\subseteq G_{v^{\prime}}$. Then for any $u\in
N_{\ell,k;B}(v)$ we have
$\nu_{B}(u,v^{\prime})=\prod_{i\in\overline{G}_{v^{\prime}}}\nu_{i}(u_{i},v^{\prime}_{i})=\prod_{i\in\overline{G}_{v^{\prime}}}\nu_{i}(v_{i},v^{\prime}_{i})$
and since there are totally $\prod_{i\in G_{v^{\prime}}}b_{i}$ such words $u$,
the left side of equation (7) equals

$\displaystyle\prod_{i\in
G_{v}}b_{i}\prod_{i\in\overline{G}_{v^{\prime}}}\nu_{i}(v_{i},v^{\prime}_{i})$
$\displaystyle=(-1)^{|G_{v}|}\prod_{i\in G_{v}}\nu_{i}(g,g)\prod_{i\in
G_{v^{\prime}}\setminus
G_{v}}\nu_{i}(v_{i},g)\prod_{i\in\overline{G}_{v^{\prime}}}\nu_{i}(v_{i},v^{\prime}_{i})$
$\displaystyle=(-1)^{\ell-k}\prod_{i=1}^{\ell}\nu_{i}(v_{i},v^{\prime}_{i})$

which equals $(-1)^{\ell-k}\nu_{B}(v,v^{\prime})$ as required.

Case (b). Suppose that $G_{v}\not\subseteq G_{v^{\prime}}$, consequently
$G_{v}\setminus G_{v^{\prime}}\neq\emptyset$. Now for any $i\in G_{v}\setminus
G_{v^{\prime}}$ we have $\nu(v_{i},v^{\prime}_{i})=0$, thus the right side of
(7) is $0$; The following argument shows that the left side is $0$ as well:
The nonzero summands in the left side of (7) are obtained from elements $u\in
X$ where the subset $X\subseteq\Sigma_{B}$ is given by

$X=\\{u\in\Sigma_{B}:u_{i}\leq v_{i}{\rm\,\,for\,\,}i\in G_{v}\setminus
G_{v^{\prime}}{\rm\,\,and\,\,}u_{i}=v_{i}{\rm\,\,for\,\,}i\in\overline{G}_{v}\\}.$

Thus we obtain

$\displaystyle\sum_{u\in N_{\ell k;B}(v)}\nu_{B}(u,v^{\prime})$
$\displaystyle=\sum_{u\in X}\nu_{B}(u,v^{\prime})$ $\displaystyle=\sum_{u\in
X}\prod_{i=1}^{\ell}\nu_{i}(u_{i},v^{\prime}_{i})$ $\displaystyle=\sum_{u\in
X}\left(\prod_{i\in\overline{G}_{v}}\nu_{i}(u_{i},v^{\prime}_{i})\prod_{i\in
G_{v}\setminus G_{v^{\prime}}}\nu_{i}(u_{i},v^{\prime}_{i})\prod_{i\in
G_{v}\cap G_{v^{\prime}}}\nu_{i}(u_{i},g)\right)$
$\displaystyle=\left(\prod_{i\in\overline{G}_{v}}\nu_{i}(v_{i},v^{\prime}_{i})\right)\left(\prod_{i\in
G_{v}\setminus
G_{v^{\prime}}}\sum_{u_{i}=0}^{v^{\prime}_{i}}\nu_{i}(u_{i},v^{\prime}_{i})\right)\left(\prod_{i\in
G_{v}\cap G_{v^{\prime}}}b_{i}\right)$

which is $0$ because for any $i\in G_{v}\setminus G_{v^{\prime}}$ we have
$\sum_{u_{i}=0}^{v^{\prime}_{i}}\nu_{i}(u_{i},v^{\prime}_{i})=\sum_{u_{i}=0}^{v^{\prime}_{i}-1}1-v^{\prime}_{i}=0.$
Thus (7) is true in either case.

$\Box$

###### Definition 13

. Let $u\in\Sigma_{B}$ and $v\in\Delta_{B}$. Then $P(u,v)$ and $Q(u,v)$ are
defined as below

$\displaystyle P(u,v)$ $\displaystyle=\\{i:1\leq i\leq\ell,v_{i}\neq
g,v_{i}=u_{i}\\}$ $\displaystyle Q(u,v)$ $\displaystyle=\\{i:1\leq
i\leq\ell,v_{i}\neq g,v_{i}\neq u_{i}\\}$

We denote $P(u,v)$ and $Q(u,v)$ by $P$ and $Q$, respectively, if there is no
danger of confusion.

With the above definition, it is obvious that
$|P(u,v)|+|Q(u,v)|=|\overline{G}_{v}|.$ Particularly, if $v\in V_{\ell,k}$ and
$|P|=p$ then $|Q|=k-p$.

###### Proposition 3

. Let $u\in\Sigma_{B}$ and $v\in\Delta_{B}$. Recall the notation of Definition
13.

  * (i)

For $1\leq i\leq\ell$, let

$\phi_{i}(u,v)=\sum_{j=\max\\{1,v_{i}\\}}^{b_{i}-1}\frac{\nu_{i}(v_{i},j)\nu_{i}(u_{i},j)}{j(j+1)}.$

Then we have

$\phi_{i}(u,v)=\left\\{\begin{array}[]{ll}\frac{b_{i}-1}{b_{i}},&\hbox{if
$i\in P$;}\\\ \\\ \frac{-1}{b_{i}},&\hbox{otherwise, i.e. if }i\in
Q.\end{array}\right.$

  * (ii)

Let $G$ be a given subset of $[\ell]$ with $G_{v}\subseteq G$. Then the
following identity holds

${\displaystyle\sum_{v^{\prime}\in\Gamma_{B}\,\,,G_{v^{\prime}}=G}\frac{\nu_{B}(v,v^{\prime})\nu_{B}(u,v^{\prime})}{{\displaystyle\prod_{i\in\overline{G}_{v^{\prime}}}(v^{\prime}_{i}+{v^{\prime}_{i}}^{2})}}}=\frac{\displaystyle(-1)^{|Q\setminus
G|+|G_{v}|}\prod_{i\in G_{v}}b_{i}\prod_{i\in P\setminus
G}(b_{i}-1)}{\displaystyle\prod_{i\in\overline{G}}b_{i}}.$ (8)

###### Proof.

  * (i)

The proof if this part is easy and left to the reader.

  * (ii)

Note that if $G_{v}\subseteq G_{v^{\prime}}=G$, it is easily obtained that

$\nu_{B}(v,v^{\prime})\,\nu_{B}(u,v^{\prime})=(-1)^{|G_{v}|}\prod_{i\in
G_{v}}b_{i}\prod_{i\in\overline{G}}\nu_{i}(v_{i},v^{\prime}_{i})\,\nu_{i}(u_{i},v^{\prime}_{i})$

hence if we denote by $S$ the left side of (8), we obtain

$\displaystyle S$ $\displaystyle=(-1)^{|G_{v}|}{\displaystyle\prod_{i\in
G_{v}}b_{i}}{\displaystyle\sum_{v^{\prime}\in\Gamma_{B}\,\,,G_{v^{\prime}}=G}\,\,\prod_{i\in\overline{G}}\frac{{\nu_{i}(v_{i},v^{\prime}_{i})\nu_{i}(u_{i},v^{\prime}_{i})}}{{v^{\prime}_{i}(v^{\prime}_{i}+1)}}}$
$\displaystyle=(-1)^{|G_{v}|}{\displaystyle\prod_{i\in
G_{v}}b_{i}\prod_{i\in\overline{G}}\,\,\sum_{j=\max\\{1,v_{i}\\}}^{b_{i}-1}\frac{\nu_{i}(v_{i},j)\nu_{i}(u_{i},j)}{j(j+1)}}$
$\displaystyle=(-1)^{|G_{v}|}{\displaystyle\prod_{i\in
G_{v}}b_{i}\prod_{i\in\overline{G}}\phi_{i}(u,v)}$

Thus by part (i), we get

$\displaystyle S$ $\displaystyle=(-1)^{|G_{v}|}{\displaystyle\prod_{i\in
G_{v}}b_{i}\prod_{i\in\overline{G}\cap
Q}\frac{-1}{b_{i}}\prod_{i\in\overline{G}\cap P}\frac{b_{i}-1}{b_{i}}}$
$\displaystyle=\frac{\displaystyle(-1)^{|Q\setminus G|+|G_{v}|}\prod_{i\in
G_{v}}b_{i}\prod_{i\in P\setminus
G}(b_{i}-1)}{\displaystyle\prod_{i\in\overline{G}}b_{i}}.$

$\Box$

##  4 Orthonormal nonzero eigendecomposition of the matrices $A_{\ell
k;B}A_{\ell k;B}^{\top}$ and $A_{\ell k;B}^{\top}A$

In this section we give an orthonormal nonzero eigendecomposition of the
matrices $A_{\ell k;B}A_{\ell k;B}^{\top}$ and $A_{\ell k;B}^{\top}A$.
Eigenvectors of these matrices are the elementary symmetric polynomials and
the entries of the corresponding eigenvectors are given in terms of the
function $\nu_{B}$. Using the properties of $\nu_{B}$ we show that these
eigenvectors are mutually orthogonal.

###### Definition 14

. Let $n,k\leq\ell$ be integers. Given $B=(b_{1},\ldots,b_{\ell})$ and
$v^{\prime}\in V^{\prime}_{\ell,n;B}$, we define the column vector ${\bf
x}_{v^{\prime}}^{\ell,k,n}$ as a vector whose rows are indexed by the elements
of $V_{\ell,k;B}$ with entries ${\bf
x}_{v^{\prime}}^{\ell,k,n}(w)=(-1)^{\ell-k}\nu_{B}(w,v^{\prime})$. The column
vector ${\bf z}_{v^{\prime}}^{\ell,n}$ is then defined as ${\bf
z}_{v^{\prime}}^{\ell,n}={\bf x}_{v^{\prime}}^{\ell,\ell,n}$; In other words,
${\bf z}_{v^{\prime}}^{\ell,n}$ is a column vector whose rows are indexed by
elements $u$ of $\Sigma_{B}$ with entries ${\bf
z}_{v^{\prime}}^{\ell,n}(u)=\nu_{B}(u,v^{\prime})$. When there is no need to
emphasize on the parameters $\ell$, $k$ and $n$, we simply write ${\bf
x}_{v^{\prime}}$ and ${\bf z}_{v^{\prime}}$.

###### Proposition 4

. Let $v^{\prime}\in\Gamma_{B}$ and $n=|{\overline{G}}_{v^{\prime}}|$. Then
the following identity holds:

$\parallel{\bf
x}_{v^{\prime}}^{\ell,k,n}\parallel^{2}=S_{\ell-k}(B(G_{v^{\prime}}))\prod_{i\in{\overline{G}}_{v^{\prime}}}(v^{\prime}_{i}+{v^{\prime}_{i}}^{2})\prod_{i\in
G_{v^{\prime}}}b_{i}$

###### Proof.

See proposition 1 (ii) $\Box$

The following proposition contains a generalization of Proposition 2 of [7]:

###### Proposition 5

. Let $0\leq k\leq\ell$, $0\leq n\leq\ell$ and $v^{\prime}\in V^{\prime}_{\ell
n}$. The following matrix identities hold.

  * (i)

$A_{\ell k;B}^{\top}{\bf x}_{v^{\prime}}^{\ell
kn}=S_{\ell-k}(B(G_{v^{\prime}}))\,{\bf z}_{v^{\prime}}^{\ell n}$.

  * (ii)

$A_{\ell k;B}{\bf z}_{v^{\prime}}^{\ell n}={\bf x}_{v^{\prime}}^{\ell kn}$.

  * (iii)

$A_{\ell k;B}A_{\ell k;B}^{\top}{\bf x}_{v^{\prime}}^{\ell
kn}=S_{\ell-k}(B(G_{v^{\prime}}))\,{\bf x}_{v^{\prime}}^{\ell kn}$.

  * (iv)

$A_{\ell k;B}^{\top}A_{\ell k;B}{\bf z}_{v^{\prime}}^{\ell
n}=S_{\ell-k}(B(G_{v^{\prime}}))\,{\bf z}_{v^{\prime}}^{\ell n}$.

  * (v)

For any two distinct words $v\in V^{\prime}_{\ell n_{1}}$ and $u\in
V^{\prime}_{\ell n_{2}}$, the vectors ${\bf x}_{v}^{\ell kn_{1}}$ and ${\bf
x}_{u}^{\ell kn_{2}}$ are orthogonal.

  * (vi)

For any two distinct words $v\in V^{\prime}_{\ell n_{1}}$ and $u\in
V^{\prime}_{\ell n_{2}}$, the vectors ${\bf z}_{v}^{\ell n_{1}}$ and ${\bf
z}_{u}^{\ell n_{2}}$ are orthogonal.

###### Proof.

The proofs of (i) and (ii) are concluded from definitions of ${\bf
x}_{v^{\prime}}$ and ${\bf z}_{v^{\prime}}$ and Proposition 2. Combining (i)
and (ii) yields (iii) and (iv). The proofs of (v) is concluded from
Proposition 1(ii). The same proposition yields part (vi) by setting $k=\ell$.
$\Box$

###### Theorem 1

. Let $0\leq k\leq\ell$. Then

  * (i)

The set $\\{S_{\ell-k}(B(G_{v^{\prime}})):v^{\prime}\in
V^{\prime}_{\ell,n;B},\,0\leq n\leq\ell\\}\\}$ consists of all eigenvalues of
the matrix $A_{\ell,k;B}^{\top}A_{\ell,k;B}$ and the set $\\{{\bf
z}_{v^{\prime}}^{\ell n}:v^{\prime}\in V^{\prime}_{\ell,n;B},\,0\leq
n\leq\ell\\}$ is a complete set of eigenvectors corresponding to eigenvalues
of $A_{\ell,k;B}^{\top}A_{\ell,k;B}$. Moreover, these eigenvectors are
pairwise orthogonal.

  * (ii)

The set $\\{S_{\ell-k}(B(G_{v^{\prime}})):v^{\prime}\in V^{\prime}_{\ell,\leq
k;B}\\}$ consists of all non-zero eigenvalues of the matrix
$A_{\ell,k;B}A_{\ell,k;B}^{\top}$. The set $\\{{\bf x}_{v^{\prime}}^{\ell
kn}:v^{\prime}\in V^{\prime}_{\ell,\leq k;B}\\}$ is a complete set of
eigenvectors corresponding to aforementioned nonzero eigenvalues. Moreover,
these eigenvectors are pairwise orthogonal.

###### Proof.

  * (i)

First we note that for any $v^{\prime}\in V^{\prime}_{\ell,n;B},0\leq
n\leq\ell$, $\,{\bf z}_{v^{\prime}}^{\ell n}$ is a nonzero vector. By
Proposition 5 (iv), for any $v^{\prime}\in\Gamma_{B}$, ${\bf
z}_{v^{\prime}}^{\ell n}$ is an eigenvector of
$A_{\ell,k;B}^{\top}A_{\ell,k;B}$ corresponding to the eigenvalue
$S_{\ell-k}(B(G_{v^{\prime}}))$. By Proposition 5 (vi), these eigenvectors are
pairwise orthogonal. Since $|\\{{\bf z}_{v^{\prime}}^{\ell n}:v^{\prime}\in
V^{\prime}_{\ell,n;B},\,0\leq n\leq\ell\\}|=|\Gamma_{B}|$ and
$|\Gamma_{B}|=|\Sigma_{B}|$ equals the size of the matrix
$A_{\ell,k;B}^{\top}A_{\ell,k;B}$, we conclude that $\\{{\bf
z}_{v^{\prime}}^{\ell n}:v^{\prime}\in V^{\prime}_{\ell,n;B},\,0\leq
n\leq\ell\\}$ is a complete set of eigenvectors corresponding to eigenvalues
of $A_{\ell,k;B}^{\top}A_{\ell,k;B}$, as required.

  * (ii)

The set of all non-zero eigenvalues of $A_{\ell,k;B}A_{\ell,k;B}^{\top}$ is
the same as the set of all non-zero eigenvalues of
$A_{\ell,k;B}^{\top}A_{\ell,k;B}$. In part (i), we obtained the complete set
of eigenvalues of $A_{\ell,k;B}^{\top}A_{\ell,k;B}$. On the other hand, if
$0\leq n\leq\ell$ and $v^{\prime}\in V^{\prime}_{\ell,n;B}$, then
$S_{\ell-k}(B(G_{v^{\prime}}))=0$ holds if and only if $k<n\leq\ell$. Hence,
the set $\\{S_{\ell-k}(B(G_{v^{\prime}})):v^{\prime}\in V^{\prime}_{\ell,\leq
k;B}\\}$ consists of all non-zero eigenvalues of the matrix
$A_{\ell,k;B}A_{\ell,k;B}^{\top}$ as well as the matrix
$A_{\ell,k;B}^{\top}A_{\ell,k;B}$. Moreover, using Proposition 5 (iii), the
corresponding eigenvectors are $\\{{\bf x}_{v^{\prime}}^{\ell
kn}:v^{\prime}\in V^{\prime}_{\ell,\leq k;B}\\}$ and these vectors are
pairwise orthogonal.

$\Box$

The following corollary is a straight conclusion of Theorem 1.

###### Corollary 1

. The set $\\{{\bf z}_{v^{\prime}}^{\ell n}:v^{\prime}\in
V^{\prime}_{\ell,n;B},\,k<n\leq\ell\\}$, is a basis for the null-space of the
matrix $A_{\ell,k;B}^{\top}A_{\ell,k;B}$.

Using Fact 3 in Section 5.6 of [5] and Theorem 1, the following corollary
gives the reduced SVD of $A_{\ell,k;B}$.

###### Corollary 2

. Let $r={\rm rank}(A_{\ell,k;B}^{\top}A_{\ell,k;B})=|V^{\prime}_{\ell,\leq
k;B}|$,
$\\{u_{1},u_{2},\ldots,u_{r}\\}=\\{\frac{1}{S_{\ell-k}(B(G_{v^{\prime}}))}{\bf
x}_{v^{\prime}}^{\ell kn}:v^{\prime}\in V^{\prime}_{\ell,\leq k;B}\\}$ and
$\\{v_{1},v_{2},\ldots,v_{r}\\}=\\{{\bf z}_{v^{\prime}}^{\ell n}:v^{\prime}\in
V^{\prime}_{\ell,\leq k;B}\\}$. Then the reduced SVD of $A_{\ell,k;B}$ is
given by $A_{\ell,k;B}=U\Sigma V$, where the columns of $U$ are vectors
$u_{i}$, ($1\leq i\leq r$) and the columns of $V$ are vectors $v_{i}$, ($1\leq
i\leq r$) and $\Sigma$ is an $r\times r$ diagonal matrix, whose diagonal
entries are the corresponding nonzero eigenvalues of the matrix
$A_{\ell,k;B}A^{\top}_{\ell,k;B}$.

###### Definition 15

. Given $B=(b_{1},\ldots,b_{\ell})$, we define $\Upsilon_{\ell,k;B}$ as a
matrix whose rows and columns are indexed by the elements of $V_{\ell,k;B}$
and $V^{\prime}_{\ell,\leq k;B}$ respectively and whose entries are given by
$\Upsilon_{\ell,k;B}(w,v^{\prime})=(-1)^{|w|-|w|_{g}}\nu_{B}(w,v^{\prime})$.
In other words, the columns of $\Upsilon_{\ell,k;B}$ are exactly the vectors
${\bf x}_{v^{\prime}}$ for $v^{\prime}\in V^{\prime}_{\ell,\leq k;B}$. Also we
define the matrix $\Lambda$ by $\Lambda={\rm
diag}(S_{\ell-k}(B(G_{v^{\prime}})))_{v^{\prime}\in V^{\prime}_{\ell,\leq
k;B}}$.

###### Remark 4

. Using Lemma 4 (ii) and Theorem 1, we obtain an orthonormal nonzero
eigendecomposition for $A_{\ell,k;B}A_{\ell,k;B}^{\top}$.

##  5 Bases for the null space and the row space of $A_{\ell,k;B}$

In this section we give concrete bases for the null space and the row space of
$A_{\ell,k;B}$. The basis for the null space is obtained just as a corollary
of the arguments of the Section 4. The basis for the row space is obtained by
a proper selection of some rows of $A_{\ell,k;B}$; This gives a combinatorial
interpretation for the previous formula about the rank of $A_{\ell,k;B}$; The
process of finding a basis for the row space of the matrix $A_{\ell,k;B}$ is
similar to the one about incidence matrices presented in [16].

###### Theorem 2

. Let $0\leq k\leq\ell$. Then

  * (i)

The set $\\{{\bf z}_{v^{\prime}}^{\ell n}:v^{\prime}\in
V^{\prime}_{\ell,n;B},\,k<n\leq\ell\\}$, is a basis for the null-space of the
matrix $A_{\ell,k;B}$.

  * (ii)

The matrix $A_{\ell,\leq k;B}$ has the same row space as $A_{\ell,k;B}$ and
${\rm rank}\,(A_{\ell,k;B})=R_{k}(B)$. For $w\in V_{\ell,\leq k;B}$ denote by
${\bf r}_{w}$ the row of $A_{\ell,\leq k;B}$ indexed $w$. Then the set
$\\{{\bf r}_{w}:w\in V^{\prime}_{\ell,\leq k;B}\\}$ is a basis for the row
space of $A_{\ell,k;B}$.

###### Proof.

  * (i)

First we observe that the vector ${\bf x}_{v^{\prime}}^{\ell kn}$ is the zero
vector if and only if $k<n\leq\ell$. Therefore, we have $\\{{\bf
z}_{v^{\prime}}^{\ell n}:v^{\prime}\in
V^{\prime}_{\ell,n;B},\,k<n\leq\ell\\}\subseteq{\rm null}(A_{\ell,k;B})$. Now,
considering ${\rm null}(A_{\ell,k;B})\subseteq{\rm
null}(A_{\ell,k;B}^{\top}A_{\ell,k;B})$ and using Corollary 1, we conclude
that ${\rm null}(A_{\ell,k;B})=\\{{\bf z}_{v^{\prime}}^{\ell n}:v^{\prime}\in
V^{\prime}_{\ell,n;B},\,k<n\leq\ell\\}$, as required.

  * (ii)

Let $1\leq i\leq k$ and $v\in V_{\ell,i-1;B}$. Let $v_{1}=g$, say $v=gs$ with
$s\in V_{\ell,i-1;B^{\prime\prime}},$ where
$B^{\prime\prime}=(b_{2},\ldots,b_{\ell})$. If $v=gs$ is matchable with some
$u\in\Sigma_{B}$, then $u$ is matchable with exactly one of the words
$0\,s,1\,s,\ldots,(b_{1}-1)\,s$; Otherwise $u$ is matchable with none of these
words. Thus we have

${\bf r}_{gs}=\sum_{i=0}^{b_{1}-1}{\bf r}_{is}$ (9)

which gives the row indexed $v\in V_{\ell,i-1;B}$ as the summation of some
rows indexed by elements $v^{\prime}\in V_{\ell,i;B}$. Similar argument is
true if we consider any gapped position of a word $v\in V_{\ell,i-1;B}$
(instead of its first position), thus we conclude ${\rm
row}(A_{\ell,i-1;B})\subseteq{\rm row}(A_{\ell,i;B})$ for each $i$, $1\leq
i\leq k$. Hence, $A_{\ell,\leq k;B}$ has the same row space as $A_{\ell,k;B}$.
In Theorem 1 (ii), we obtained a complete set of non-zero eigenvalues of
$A_{\ell,k;B}A_{\ell,k;B}^{\top}$ which yields ${\rm
rank}(A_{\ell,k;B}A_{\ell,k;B}^{\top})=|V^{\prime}_{\ell,\leq k;B}|=R_{k}(B)$.
Since ${\rm rank}(A_{\ell,k;B}A_{\ell,k;B}^{\top})$ equals ${\rm
rank}(A_{\ell,k;B})$, we obtain ${\rm rank}(A_{\ell,k;B})=R_{k}(B)$. To
provide a combinatorial interpretation of this, we first rewrite the equation
(9) in the form ${\bf r}_{0s}={\bf r}_{gs}-\sum_{i=1}^{b_{1}-1}{\bf r}_{is}$
and then generalize this as below

${\bf r}_{0^{m}s}=\sum_{t\in\Gamma_{B^{\prime}}}(-1)^{m-|t|_{g}}{\bf r}_{ts},$
(10)

where $0<m\leq\ell$,
$B^{\prime}=(b_{1},\ldots,b_{m})$,$\,\,B^{\prime\prime}=(b_{m+1},\ldots,b_{\ell})$
and $s\in\Delta_{B^{\prime\prime}}$. The proof of (10) is by induction on $m$
and left to the reader. When $s\in\Gamma_{B^{\prime\prime}}$, equation (10)
gives the row indexed by the word $v=0^{m}s\in V_{\ell,\leq k;B}\setminus
V^{\prime}_{\ell,\leq k;B}$ as a linear combination of rows indexed by some
words $v^{\prime}\in V^{\prime}_{\ell,\leq k;B}$. By a proper permutation of
the $0$ positions of $v$, it is observed that the last statement is true for
any word $v\in V_{\ell,\leq k;B}\setminus V^{\prime}_{\ell,\leq k;B}$
regardless of its positions of zeros; Hence, the set $\\{{\bf r}_{w}:w\in
V^{\prime}_{\ell,\leq k;B}\\}$ is a generator for the row space of
$A_{\ell,k;B}$. Now, using ${\rm rank}(A_{\ell,k;B})=R_{k}(B)$, we conclude
that $\\{{\bf r}_{w}:w\in V^{\prime}_{\ell,\leq k;B}\\}$ is a basis for the
row space of $A_{\ell,k;B}$.

$\Box$

##  6 Computing the entries of the matrices $W_{\ell,k;B}$ and $H_{\ell,k;B}$

In this section we give a concrete description of the entries of matrices
$W_{\ell,k;B}$ and $H_{\ell,k;B}$, using the orthonormal nonzero
eigendecomposition of the matrices $A_{\ell,k;B}A_{\ell,k;B}^{\top}$.

###### Theorem 3

. Let $u\in\Sigma_{B}$, $v\in V_{\ell,k;B}$. Moreover, with notation of
Definition 13, let $P=P(u,v)$ and $Q=Q(u,v)$. Then the entry
$W_{\ell,k;B}(u,v)$, the Moore-Penrose pseudo-inverse of $A_{\ell,k;B}$, is
given as below

$W_{\ell,k;B}(u,v)=\frac{1}{\displaystyle\prod_{i\in\overline{G}_{v}}b_{i}}\,\,\sum_{G,\,G_{v}\subseteq
G\subseteq[\ell]}\frac{\displaystyle(-1)^{|Q\setminus G|}\prod_{i\in
P\setminus G}(b_{i}-1)}{S_{\ell-k}(B(G))}$ (11)

###### Proof.

For $v^{\prime}\in V^{\prime}_{\ell,\leq k}$, let
$d_{v^{\prime}}=\frac{1}{||{\bf x}_{v^{\prime}}||^{2}\lambda_{v^{\prime}}}$.
By Lemma 4 and the definitions of $A_{\ell,k;B}$ and $\Upsilon_{\ell,k;B}$ we
obtain

$\displaystyle W_{\ell,k;B}(u,v)$ $\displaystyle=\sum_{y\in
M_{\ell,k;B}(u)}\sum_{v^{\prime}\in V^{\prime}_{\ell,\leq
k}}\nu_{B}(v,v^{\prime})\,\nu_{B}(y,v^{\prime})d_{v^{\prime}}$
$\displaystyle=\sum_{v^{\prime}\in V^{\prime}_{\ell,\leq
k}}\nu_{B}(v,v^{\prime})\,d_{v^{\prime}}\sum_{y\in
M_{\ell,k;B}(u)}\nu_{B}(y,v^{\prime})$ $\displaystyle=\sum_{v^{\prime}\in
V^{\prime}_{\ell,\leq
k}}(-1)^{\ell-k}\nu_{B}(v,v^{\prime})\,d_{v^{\prime}}\,S_{\ell-k}(B(G_{v^{\prime}}))\,\nu_{B}(u,v^{\prime})~{}~{}~{}\hbox{(by
(\ref{nuId1}))}$

Replacing $d_{v^{\prime}}$ using Proposition 4, we obtaine

$\displaystyle W_{\ell,k;B}(u,v)$
$\displaystyle=(-1)^{\ell-k}\sum_{v^{\prime}\in V^{\prime}_{\ell,\leq
k}}\frac{\nu_{B}(v,v^{\prime})\,\nu_{B}(u,v^{\prime})}{S_{\ell-k}(B(G_{v^{\prime}})){\displaystyle\prod_{i\in\overline{G}_{v^{\prime}}}(v^{\prime}_{i}+{v^{\prime}_{i}}^{2})\prod_{i\in
G_{v^{\prime}}}b_{i}}}$ $\displaystyle=(-1)^{\ell-k}\sum_{G,G_{v}\subseteq
G}\,\,\,\sum_{v^{\prime}\in V^{\prime}_{\ell,\leq
k},G_{v^{\prime}}=G}\frac{\nu_{B}(v,v^{\prime})\,\nu_{B}(u,v^{\prime})}{S_{\ell-k}(B(G_{v^{\prime}})){\displaystyle\prod_{i\in\overline{G}_{v^{\prime}}}(v^{\prime}_{i}+{v^{\prime}_{i}}^{2})\prod_{i\in
G_{v^{\prime}}}b_{i}}}$ $\displaystyle=(-1)^{\ell-k}\sum_{G,\,G_{v}\subseteq
G\subseteq[\ell]}\,\frac{1}{S_{\ell-k}(B(G)){\displaystyle\prod_{i\in
G}b_{i}}}\,\,\sum_{v^{\prime}\in\Gamma_{B}\,,G_{v^{\prime}}=G}\frac{\nu_{B}(v,v^{\prime})\,\nu_{B}(u,v^{\prime})}{{\displaystyle\prod_{i\in\overline{G}_{v^{\prime}}}(v^{\prime}_{i}+{v^{\prime}_{i}}^{2})}}$
$\displaystyle=\frac{1}{\displaystyle\prod_{i\in\overline{G}_{v}}b_{i}}\,\,\sum_{G,\,G_{v}\subseteq
G\subseteq[\ell]}\frac{\displaystyle(-1)^{|Q\setminus G|}\prod_{i\in
P\setminus G}(b_{i}-1)}{S_{\ell-k}(B(G))}~{}~{}~{}\hbox{(by
(\ref{fracNuId}))}~{}~{}~{}$

$\Box$

###### Theorem 4

. The sum of entries of any rows (columns) of the matrix
$H_{\ell,k;B}:=W_{\ell,k;B}A_{\ell,k;B}$ equals $1$. Furthermore, for any
$u,w\in\Sigma_{B}$, the entry $H_{\ell,k;B}(u,w)$ is given as below, where by
using Definition 13, $P=P(u,w)$ and $Q=Q(u,w)$.

$H_{\ell,k;B}(u,w)=\frac{1}{\displaystyle\prod_{i=1}^{\ell}b_{i}}\,\,\sum_{G\subseteq[\ell],\,\,\ell-k\leq|G|}{\displaystyle(-1)^{|Q\setminus
G|}\prod_{i\in P\setminus G}(b_{i}-1)}$ (12)

###### Proof.

To compute the sum of entries of each row (column) of the matrix $H$, we
observe that ${\bf z}_{gg\cdots g}^{\ell k0}={\bf j}$. Now, using Proposition
5 (iv) and Lemma 3, we have $H{\bf j}={\bf j}$, as desired.

To calculate the entry $H_{\ell,k;B}(u,w)$ of $H$, firstly note that if $v\sim
w$ then for any subset $G_{v}\subseteq G\subseteq[\ell]$ we have
$P(u,v)\setminus G=P(u,w)\setminus G$ and $Q(u,v)\setminus G=Q(u,w)\setminus
G$. Secondly, by $H_{\ell,k;B}=W_{\ell,k;B}A_{\ell,k;B}$ we have

$H_{\ell,k;B}(u,w)=\sum_{v\in V_{\ell,k;B},\,\,v\sim w}W_{\ell,k;B}(u,v)$

Thirdly, the result of Theorem 3, is rewritten as

$W_{\ell,k:B}(u,v)=\frac{1}{\displaystyle\prod_{i=1}^{\ell}b_{i}}\,\,\sum_{G,\,G_{v}\subseteq
G\subseteq[\ell]}\frac{\displaystyle(-1)^{|Q(u,v)\setminus
G|}{\displaystyle\prod_{i\in G_{v}}b_{i}}\prod_{i\in P(u,v)\setminus
G}(b_{i}-1)}{S_{\ell-k}(B(G))}$

Thus by the two last formulas we obtain

$\displaystyle H_{\ell,k;B}(u,w)$
$\displaystyle=\frac{1}{\displaystyle\prod_{i=1}^{\ell}b_{i}}\sum_{v\in
V_{\ell,k;B},\,\,v\sim w}\,\,\,\,\sum_{G,\,G_{v}\subseteq
G\subseteq[\ell]}\frac{\displaystyle(-1)^{|Q(u,v)\setminus
G|}{\displaystyle\prod_{i\in G_{v}}b_{i}}\prod_{i\in P(u,v)\setminus
G}(b_{i}-1)}{S_{\ell-k}(B(G))}$
$\displaystyle={\displaystyle\frac{1}{\prod_{i=1}^{\ell}b_{i}}}\,\sum_{G\subseteq[\ell],\,\ell-k\leq|G|}\,\,\,\,\sum_{v\in
V_{\ell,k;B},\,v\sim w,G_{v}\subseteq
G}\frac{\displaystyle(-1)^{|Q(u,v)\setminus G|}{\displaystyle\prod_{i\in
G_{v}}b_{i}}\prod_{i\in P(u,v)\setminus G}(b_{i}-1)}{S_{\ell-k}(B(G))}$
$\displaystyle={\displaystyle\frac{1}{\prod_{i=1}^{\ell}b_{i}}}\,\sum_{G\subseteq[\ell],\,\ell-k\leq|G|}\,\,\,\,\sum_{v\in
V_{\ell,k;B},\,v\sim w,G_{v}\subseteq
G}\frac{\displaystyle(-1)^{|Q(u,w)\setminus G|}{\displaystyle\prod_{i\in
G_{v}}b_{i}}\prod_{i\in P(u,w)\setminus G}(b_{i}-1)}{S_{\ell-k}(B(G))}$
$\displaystyle={\displaystyle\frac{1}{\prod_{i=1}^{\ell}b_{i}}}\,\sum_{G\subseteq[\ell],\,\ell-k\leq|G|}\frac{\displaystyle(-1)^{|Q(u,w)\setminus
G|}\prod_{i\in P(u,w)\setminus G}(b_{i}-1)}{S_{\ell-k}(B(G))}\sum_{v\in
V_{\ell,k;B},\,v\sim w,G_{v}\subseteq G}{\displaystyle\,\,\,\,\prod_{i\in
G_{v}}b_{i}}$

Now, considering the fact that the inner summation is exactly
$S_{\ell-k}(B(G))$, we obtain (12).  $\Box$

Acknowledgement. M. Mohammad-Noori would like to thank University of Tehran
for supporting him during his sabbatical leave at IPM. The researches of N.
Ghareghani and M. Mohammad-Noori were in part supported by grants from IPM
(No. 94050016 and No. 95050129).

## References

  * [1] P. J. Cameron, (2003) Notes on Counting. http://www.maths.qmul.ac.uk/ pjc/notes
/counting.pdf. Accessed 25 January 2012.

  * [2] D. A Cox, J. Little, D. O’Shea, Ideals, varieties, and algorithms: an introduction to computational algebraic geomerty and commutative algebra, (3rd edition), Springer, 2007.
  * [3] Ph. Delsarte, Beyond the orthogonal array concept, European Journal of Combinatorics (2004), 25, 187-198.
  * [4] Ph. Delsarte, Association schemes and $t$-designs in regular semilattices, Journal of Combinatorial Theory Series A (1976), 20, 230-243.
  * [5] L. Han and M. Neumann, Inner Product Spaces, Orthogonal Projection, Least Squares and Singular Value Decomposition In: Leslie Hogben (eds) Handbook of Linear Algebra, 2nd Edition (Discrete Mathematics and Its Applications) Boca Raton, FL: CRC Press; (2013).
  * [6] M. Ghandi, D. Lee, M. Mohammad-Noori, and M. A. Beer, Enhanced regulatory sequence prediction using gapped k-mer features, PLoS Comput Biol, 2014. 10 (7): p. e1003711
  * [7] M. Ghandi, M. Mohammad-Noori, and M. A. Beer, Robust $k$-mer frequency estimation using gapped $k$-mers, Journal of mathematical biology. (2014), 60, Issue 2 , 469-500.
  * [8] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science (Second Edition), Addison Wesley Publishing Company, 1994.
  * [9] D. Lee, D. U. Gorkin, M. Baker, B. J. Strober, A. L. Asoni, A. S. McCallion and M. A. Beer, A method to predict the impact of regulatory variants from DNA sequence, Nature Genetics (August 2015), 47, no. 8 : 955-961. doi:10.1038/ng.3331.
  * [10] M. Marcus and H. Minc, Introduction to Linear Algebra. New York: Dover, p. 182, 1988.
  * [11] M. Marcus and H. Minc, ”Positive Definite Matrices.”4.12 in A Survey of Matrix Theory and Matrix Inequalities. New York: Dover, p. 69, 1992.
  * [12] A. Mo, Ch. Luo, F. P. Davis, E. A. Mukamel, G. L. Henry, J. R. Nery, M. A. Urich, et al, Epigenomic landscapes of retinal rods and cones, eLife (March 7, 2016), 5: e11613. doi:10.7554/eLife.11613.
  * [13] B. Morgenstern, B. Zhu, S. Horwege and Ch. A. Leimeister, Estimating evolutionary distances between genomic sequences from spaced-word matches, Algorithms for Molecular Biology (2015), 10: 5. doi:10.1186/s13015-015-0032-x.
  * [14] P. Terwilliger, The incidence algebra of a uniform poset In: Codeng Theory and Design Theory Part I: Coding Theory, IMA Volumes in Mathematics and its Applications, vol. (20), Springer, New York, 1990, 193-212.
  * [15] Chaudhari HG and Cohen BA, Local sequence features that influence AP-1 cis-regulatory activity, Genome Res. 2018 Feb;28(2):171-181. doi: 10.1101/gr.226530.117. Epub 2018 Jan 5.
  * [16] R. M. Wilson, A diagonal form for the incidence matrices of t-subsets vs. k-subsets. European Journal of Combinatorics (1990), 11, 609-615.