%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Packed matrices and related Hopf algebras}
\label{SMQ}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The combinatorial objects}

In the sequel, we will represent different kinds of diagrams using matrices to
emphasize the parallel between this construction and the construction of
$\MQSym$ (\cite{DHT}).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Set packed matrices}

Since the computations are the same in many cases, let us begin with the most
general case and explain how one recovers the other cases by algebraic means.
Let us consider the set $\lldiag$ of bipartite graphs with white and black
vertices, and edges, all three labelled by intervals $[1,p]$. The diagrams
$\ldiag$ are obtained by erasing the numbers the edges of one such element.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsubsection{Set packed matrices}

The set $\lldiag$ is in direct bijection with \emph{set packed matrices}, that
are matrices containing disjoint subsets of $[1,n]$ for some $n\in\N$ with
no line or column filled with empty sets such that the union of all subsets is
$[1,n]$ itself. The bijection consists in putting $k$ in the cell $(i,j)$ of
the matrix if the edge labelled $k$ connects the white dot labelled $i$ with
the black dot labelled $j$.
Figure~\ref{mat-sc} shows an example of such a matrix.

\begin{figure}[ht]
\begin{equation*}
\left(
 \begin{array}{ccc}
  \{3\}    &\{6\} &\{2\}\\
  \emptyset&\{1,5\}   &\{4\}
  \end{array}\right)
\end{equation*}
\caption{\label{mat-sc}A set packed matrix.}
\end{figure}

Note that set packed matrices are in bijection with pairs of set compositions,
or, ordered partition of $[1,n]$: given a set packed matrix, compute the
ordered sequence of the unions of the elements in the same row (resp. column).
For example, the set packed matrix of Figure~\ref{mat-sc} gives rise to the
two set compositions $\{2,3,6\},\{1,4,5\}$ and
$\{3\},\{1,5,6\},\{2,4\}$. Given two set compositions $\Pi$ and $\Pi'$, define
$M_{ij}:=\Pi_i\cap\Pi'_j$.

It is then easy to compute that the generating series depending on $n$ of such
matrices is given by the square of the ordered Bell numbers, that is
sequence A122725 in~\cite{Slo}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Integer packed matrices}

As already said, if one forgets the ordering of the edges of an element of
$\lldiag$, one recovers an element of $\ldiag$. Its matrix representation
is an \emph{integer packed matrix}, that is, a matrix with no line or column
filled with zeros. The encoding is simple: $m_{ij}$ is equal to the number of
edges between the white spot labelled $i$ and the black spot labelled $j$.
Note that, from the matrix point of view, it consists in replacing the subsets
by their cardinality.
Figure~\ref{mat-int} shows an example of such a matrix.

\begin{figure}[ht]
\begin{equation*}
\left(
 \begin{array}{ccc}
 1&1&1\\
 0&2&1\\
 \end{array}\right)
\end{equation*}
\caption{\label{mat-int}An integer packed matrix.}
\end{figure}

The generating series of such matrices depending on $n$ is given by sequence
A120733 of~\cite{Slo}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Other packed matrices}

During our study, we will also need diagrams where one forgets about the labels
of the white spots, or about the labels of the black spots, or about all labels.
Those three classes of diagrams are respectively in bijection with matrices up to a permutation
of the rows, a permutation of the columns, and simultaneous permutations of
both.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Word quasi-symmetric and symmetric functions}

Let us recall briefly the definition of two already known combinatorial
Hopf algebras that will be useful in the sequel.

%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{$\WQSym$}

We use the notations of \cite{NT}. The word quasi-symmetric
functions are the noncommutative polynomial invariants of Hivert's
quasi-symmetrizing action \cite{Hiv}
\begin{equation}
\WQSym(A):=\C\langle A \rangle^{{\mathfrak S}(A)_{QS}}.
\end{equation}

When $A$ is an infinite alphabet, $\WQSym(A)$ is a graded Hopf algebra whose
basis is indexed by set compositions, or, equivalently, packed words. Recall
that packed words are words $w$ on the alphabet $[1,k]$ where if $i\not=1$
appears in $w$, then $i-1$ also appears in $w$. The bijection between both
sets is that $w_i=j$ iff $i$ is in the $j$-th part of the set composition (see
Figure~\ref{sc-pack} for an example).

\begin{figure}[ht]
\begin{center}
$cbbadacb \qquad\longleftrightarrow\qquad [\{4,6\},\{2,3,8\},\{1,7\},\{5\}]$
\end{center}
\caption{\label{sc-pack}A packed word and its corresponding set composition.}
\end{figure}

By definition, $\WQSym$ is generated by the polynomials
\begin{equation}
\WQ_u:=\sum_{{\rm pack}(w)=u}w,
\end{equation}
where $u={\rm pack}(w)$ is the packed word having the same comparison
relations between all elements as $w$.

The product in $\WQSym$ is given by
\begin{equation}
\WQ_u\WQ_v=\sum_{w\in u\star_Wv}\WQ_w,
\end{equation}
where the convolution $u\star_Wv$ of two packed words is defined by
\begin{equation}
u\star_Wv=\sum_{w_1,w_2; w=w_1w_2\ {\rm packed}\atop {\rm pack}(w_1)=u,\
{\rm pack}(w_2)=v}w.
\end{equation}
%
The coproduct is given by
%
\begin{equation}
\Delta \WQ_w(A)= \sum_{u,v ; w\in u\ssh_W\,v} \WQ_u\otimes \WQ_v
\end{equation}
where $u\ssh_W\, v$ denotes the \emph{packed shifted shuffle} that
is the shuffle of $u$ and $v'=v[max(u)]$, that is the word $v'_i=v_i+max(u)$.

The dual algebra $\WQSym^*$ of $\WQSym$ is a subalgebra of the Parking
quasi-symmetric functions $\bf PQSym$.
This algebra has a multiplicative basis denoted by $\FQ^w$, where the product
is the shifted concatenation, that is $u. v[max(u)]$.
% Technical details
%suggest that one should better write the basis are maximally unpacked words
%instead of packed words

%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{$\WSym$}

The algebra of word symmetric functions $\WSym$, first defined by Rosas and
Sagan in~\cite{SR}, where it is called the algebra of symmetric functions in
noncommuting variables, is the Hopf subalgebra of $\WQSym$ generated by
\begin{equation}
\W_{\pi}:=\sum_{\mbox{\scriptsize sp}(u)=\pi}\WQ_{u},
\end{equation}
%
where $\mbox{sp}(u)$ is the (unordered) set partition obtained by forgetting the
order of the parts of its corresponding set composition.

Its dual $\WSym^*$ is the quotient of $\WQSym^*$
\begin{equation}
\WSym^*=\WQSym^*/_J
\end{equation}
%
where $J$ is the ideal generated by the polynomials $\FQ^u-\FQ^v$
with $u$ and $v$ corresponding to the same set partition.
We denote by $\F^{\mbox{\scriptsize sp}(u)}$ the image of $\FQ^u$ by the canonical surjection.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Hopf algebras of set packed matrices}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Set matrix quasi-symmetric functions}

The construction of the Hopf algebra $\SMQSym$ over set packed matrices is a
direct translation of the construction of $\MQSym$ (\cite{Hiv,DHT}).
Consider the linear subspace spanned by the elements $\SMQ_{M}$, where $M$
runs over the set of set packed matrices. We denote by $h(M)$ the number of
rows of $M$. Then define
\begin{equation}
\SMQ_{P} \SMQ_{Q} := \sum_{R\in\ash (P,Q)} \SMQ_R
\end{equation}

where the {\em augmented shuffle} of $P$ and $Q$,
$\ash(P,Q)$ is defined as follows: let $Q'$ be obtained from $Q$ by adding the
greatest number inside $P$ to all elements inside $Q$. Let $r$ be an
integer between $\max(p,q)$ and $p+q$, where $p=h(P)$ and $q=h(Q)$.
Insert rows of zeros in the matrices $P$ and $Q'$ so as to form
matrices $\tilde P$ and $\tilde Q'$ of height $r$. Let $R$ be
the matrix obtained by gluing $\tilde Q'$ to the right of $\tilde P$.
The set $\ash (P,Q)$ is formed by all the matrices with no row of 0's obtained
this way.

For example,
\begin{equation}
\begin{array}{l}
  \SMQ_{\mcc{\st\{3,4\}&\k8\st\{1\}\\\st\{2\}&\k8\st\emptyset}}
  \SMQ_{\mcc{\st\{2,3,4\}&\k8\st\{1\}}} =

  \SMQ_{\mcccc{
             \st\{3,4\}&\k8\st\{1\}&\k8\st\es&\k8\st\es\\
             \st\{2\}&\k8\st\es&\k8\st\es&\k8\st\es\\
             \st\es&\k8\st\es&\k8\st\{6,7,8\}&\k8\st\{5\}}}
 +\SMQ_{\mcccc{
             \st\{3,4\}&\k8\st\{1\}&\k8\st\es&\k8\st\es\\
             \st\{2\}&\k8\st\es&\k8\st\{6,7,8\}&\k8\st\{5\}}}
 \\[3mm]
\qquad\
  +\SMQ_{\mcccc{
             \st\{3,4\}&\k8\st\{1\}&\k8\st\es&\k8\st\es\\
             \st\es&\k8\st\es&\k8\st\{6,7,8\}&\k8\st\{5\}\\
             \st\{2\}&\k8\st\es&\k8\st\es&\k8\st\es}}
  +\SMQ_{\mcccc{
             \st\{3,4\}&\k8\st\{1\}&\k8\st\{6,7,8\}&\k8\st\{5\}\\
            \st\{2\}&\k8\st\es&\k8\st\es&\k8\st\es}}
  +\SMQ_{\mcccc{
             \st\es&\k8\st\es&\k8\st\{6,7,8\}&\k8\st\{5\}\\
             \st\{3,4\}&\k8\st\{1\}&\k8\st\es&\k8\st\es\\
             \st\{2\}&\k8\st\es&\k8\st\es&\k8\st\es}}.
\end{array}
\end{equation}

The coproduct $\Delta \SMQ_{M}$ is defined by
\begin{equation}
\Delta\SMQ_A=\sum_{A=\left(A_1\atop A_2\right)}
                 \SMQ_{\std(A_1)}\otimes \SMQ_{\std(A_2)},
\end{equation}
where $\std(A)$ denotes the standardized of the matrix $A$, that is the matrix
obtained by the substitution $a_i\mapsto i$, where $a_1<\cdots<a_n$ are the integers
appearing in $A$. For example,

\begin{equation}
\Delta\SMQ_{\mcc{ \st\{2,4\}&\k8\st\{1\}\\
                                    \st\{6\}&\k8\st\{3,5\}}}
=\SMQ_{\mcc{ \st\{2,4\}&\k8\st\{1\}\\
                                 \st\{6\}&\k8\st\{3,5\}}}\otimes
1+ \SMQ_{\mcc{ \st\{2,3\}&\k8\st\{1\}}}\otimes
   \SMQ_{\mcc{\st\{3\}&\k8\st\{1,2\}}}
+1\otimes
\SMQ_{\mcc{\st\{2,4\}&\k8\st\{1\}\\
                                    \st\{6\}&\k8\st\{3,5\}}}
\end{equation}

Rather than checking the compatibility between the product and the
coproduct, one can look for a realization of $\SMQSym$, here in
terms of noncommutative bi-words, that will later give useful
guidelines to select or understand homomorphisms between the
different algebras.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Realization of $\SMQSym$}

A noncommutative bi-word is a word over an alphabet of bi-letters
$\left\langle a_i\atop {\bf b}_j\right\rangle$ with $i,j\in\N$ where $a_i$
and ${\bf b}_j$ are letters of two distinct ordered alphabets $A$ and $\bf B$.
%
We will denote by $\C\left\langle A\atop{\bf B}\right\rangle$ the algebra of
the (potentially infinite) polynomials over the bi-letters
$\left\langle a\atop{\bf b}\right\rangle$ for the product $\star$ defined by
%
\begin{equation}
\left\langle u_1\atop {\bf v}_1\right\rangle\star\left\langle u_2\atop {\bf
v}_2\right\rangle=
\left\langle u_1.u_2\atop {\bf v}_1.{\bf v}_2[\max({\bf v}_1)]\right\rangle,
\end{equation}
%
where ${\bf v}_1.{\bf v}_2[k]$ denotes the concatenation of ${\bf v}_1$ with
the word ${\bf v}_2$ whose letters are shifted by $k$ and $\max({\bf v}_1)$
the maximal letter of ${\bf v}_1$.

For example,
\begin{equation}
\left\langle 142\atop236\right\rangle\star \left\langle 24\atop
31\right\rangle=\left\langle 14224\atop 23697\right\rangle
\end{equation}

\begin{lemma}
The product $\star$ is associative.
\end{lemma}

One associates to each set packed matrix the bi-word
such that its $i$th bi-letter is the coordinate in which the letter
$i$ appears in the matrix.
For example,

\begin{equation}
\mbox{bi-word}\left(\begin{array}{ccc} \{2,4\}&\{1\}\\
\{6\}&\{3,5\}
\end{array}\right)= \left\langle a_1a_1a_2a_1a_2a_2\atop
{\bf b}_2{\bf b}_1{\bf b}_2{\bf b}_1{\bf b}_2{\bf
b}_1\right\rangle.
\end{equation}
%

A bi-word is said bi-packed if its two words are packed.
The bi-packed of a bi-word is the bi-word obtained by packing its
two words.
%For example,
%
%\begin{equation}
%{\rm bipacked}\left(\left\langle a_1a_1a_3a_1a_3a_3\atop {\bf
%b}_4{\bf b}_2{\bf b}_4{\bf b}_2{\bf b}_4{\bf
%b}_2\right\rangle\right)=\left\langle a_1a_1a_2a_1a_2a_2\atop {\bf
%b}_2{\bf b}_1{\bf b}_2{\bf b}_1{\bf b}_2{\bf b}_1\right\rangle
%\end{equation}
%
The set packed matrices are obviously in bijection with the
bi-packed bi-words. Let $\left\langle u\atop {\bf v}\right\rangle$
be a bi-packed bi-word. Then

\begin{theorem}
\label{Endgr}
~

\begin{itemize}
\item The algebra $\SMQSym$ can be realized on bi-words by
\begin{equation}
\SMQ_{\left\langle u\atop {\bf v}\right\rangle}:=
\sum_{{\rm bipacked }\left\langle u'\atop {\bf v}'\right\rangle
      =\left\langle u\atop {\bf v}\right\rangle
     } \left\langle u'\atop {\bf v'}\right\rangle.
\end{equation}
\item $\SMQSym$ is a Hopf algebra.

\item $\SMQSym$ is isomorphic as a Hopf algebra to the graded endomorphisms of
$\WQSym$:
\begin{equation}
{\rm End}_{gr}\WQSym=\bigoplus_{n\in\N} \WQSym_n\otimes \WQSym^*_n
\end{equation}
through the Hopf homomorphism
\begin{equation}
\phi\left({\rm \SMQ}_{\left\langle u\atop\bf v\right\rangle}\right)=
\WQ_{u}\otimes \FQ^{\bf v}.
\end{equation}
\end{itemize}
\end{theorem}

Indeed, from the point of view of the realization, the coproduct of
$\SMQSym$ is given by the usual trick of noncommutative symmetric
functions, considering the alphabet $A$ as an ordered sum of two
mutually commuting alphabets $A'\hat+A''$, hence being a
homomorphism for the product.

%We will indifferently use bi-packed bi-words, set packet matrices and
%pairs of set compositions in our notations.
%, so that, for example

%\begin{equation}
%\begin{array}{rcl}
%\SMQ_{\left(\begin{array}{ccc} \{2,4\}&\{1\}\\ \{6\}&\{3,5\}\end{array}\right)}
%&=&
%\SMQ_{\left\langle a_1a_1a_2a_1a_2a_2\atop%
%     {\bf b}_2{\bf b}_1{\bf b}_2{\bf b}_1{\bf b}_2{\bf b}_1\right\rangle}\\
%&=&\SMQ_{([\{1,2,4\},\{3,5,6\}],[\{2,4,6\},\{1,3,5\}])}\\[5pt]
%&=&\displaystyle\sum_{i_1<i_2\atop j_1<j_2}
%   \left\langle a_{i_1}\,a_{i_1}\,a_{i_2}\,a_{i_1}\,a_{i_2}\,a_{i_2}\atop%
%   {\bf b}_{j_2}{\bf b}_{j_1}{\bf b}_{j_2}{\bf b}_{j_1}{\bf b}_{j_2}
%   {\bf b}_{j_1} \right\rangle\end{array}
%\end{equation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Set matrix half-symmetric functions}

\subsubsection{The Hopf algebra $\SMRSym$}

Let $\SMRSym$ be the subalgebra of $\SMQSym$ generated by the polynomials
$\SMR_{\pi_1,\Pi_2}$ indexed by a set partition $\pi_1$ and a set composition
$\Pi_2$ and defined by

\begin{equation}
{\rm \SMR}_{(\pi_1,\Pi_2)}
:=\sum_{{\rm sp}(\Pi_1)=\pi_1}{\rm \SMQ}_{\Pi_1,\Pi_2}.
\end{equation}

\begin{equation}
\begin{array}{rcl}{\rm \SMR}_{\{\{13\},\{4\},\{2\}\},[\{123\},\{4\}]}&=&
 {\rm \SMQ}_{\mcc{\st\{1,3\}&\k8\st\es\\\st\es&\k8\st\{4\}\\\st\{2\}&\k8\st\es}}
 %\tiny\left(\k6\begin{array}{cc}
  %\st\{1,3\}&\k8\st\es\\\st\es&\k8\st\{4\}\\\st\{2\}&\k8\st\es\end{array}\k7\right)}
   +
  {\rm \SMQ}_{\mcc{
  \st\{1,3\}&\k8\st\es\\\st\{2\}&\k8\st\es\\\st\es&\k8\st\{4\}}}
+{\rm \SMQ}_{\mcc{
  \st\es&\k8\st\{4\}\\\st\{1,3\}&\k8\st\es\\\st\{2\}&\k8\st\es}}\\
&&+{\rm \SMQ}_{\mcc{
  \st\es&\k8\st\{4\}\\\st\{2\}&\k8\st\es\\\st\{1,3\}&\k8\st\es}}
  +{\rm \SMQ}_{\mcc{
  \st\{2\}&\k8\st\es\\\st\es&\k8\st\{4\}\\\st\{1,3\}&\k8\st\es}}
+{\rm \SMQ}_{\mcc{
  \st\{2\}&\k8\st\es\\\st\{1,3\}&\k8\st\es\\\st\es&\k8\st\{4\}}}
 \end{array}
\end{equation}


Note that a pair constituted by a set partition and a set composition is
equivalent to a set packed matrix up to a permutation of its rows. Hence, the
realization on bi-words follows: for example,

\begin{equation}
{\rm \SMR}_{\{\{13\},\{4\},\{2\}\},[\{123\},\{4\}]}
=\sum_{i_1, i_2, i_3\text{ distinct}\atop j_1<j_2}
 \left\langle a_{i_1}\,a_{i_2}\,a_{i_1}\,a_{i_3}\atop
              {\bf b}_{j_1} {\bf b}_{j_1} {\bf b}_{j_1}{\bf b}_{j_2}
 \right\rangle
\end{equation}

\begin{proposition}
~

\begin{itemize}
\item $\SMRSym$ is isomorphic to $\oplus \WSym_n\otimes \WQSym_n^*$.
\item $\SMRSym$ is a co-commutative Hopf subalgebra of $\SMQSym$.
\end{itemize}
\end{proposition}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{The Hopf algebra $\SMCSym$}

Forgetting about the order of the columns instead of the rows leads to another
Hopf algebra, $\SMCSym$, a basis of which is indexed by the
pairs $(\Pi_1,\pi_2)$ ($\Pi_1$ is a set composition and $\pi_2$ is a
set partition).
It is the quotient of $\SMQSym$ by the polynomials
\begin{equation}
{\rm \SMQ}_{\Pi_1,\Pi_2}-{\rm \SMQ}_{\Pi_1,\Pi'_2}
\end{equation}
where ${\rm sp}(\Pi_2)={\rm sp}(\Pi'_2)$.
Note that this quotient can be brought down to the bi-words.
We will denote by $\alpha$ the canonical surjection:
\begin{equation}
\alpha(\SMQ_{\Pi_1,\Pi_2})=:{\rm \SMC}_{\Pi_1,{\rm sp}(\Pi_2)}
\end{equation}
The algebra $\SMCSym$ is spanned by the ${\rm \SMC}_{\Pi_1,\pi_2} $ where
$\Pi_1$ is a set composition and $\pi_2$ is a set partition.

\begin{proposition}
~

\begin{itemize}
\item $\SMCSym$ is isomorphic to $\oplus \WQSym_n\otimes \WSym_n^*$,
\item $\SMCSym$ is a Hopf algebra.
\end{itemize}
\end{proposition}

Note that both $\SMRSym$ and $\SMCSym$ have the same Hilbert series, given by
the product of ordered Bell numbers by unordered Bell numbers. This gives one
new example of two different Hopf structures on the same combinatorial set
since $\SMCSym$ is neither commutative nor cocommutative.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Set matrix symmetric functions}

The algebra $\SMSym$ of \emph{set matrix symmetric functions} is the
subalgebra of $\SMCSym$ generated by the polynomials
\begin{equation}
{\rm \SM}_{\pi_1,\pi_2}=\sum_{{\rm sp}(\Pi_1)=\pi_1}\SMR_{\Pi_1,\pi_2}
\end{equation}

For example,
\begin{equation}
{\rm \SM}_{\{\{1,3\},\{4\},\{2\}\},\{\{1,2,3\},\{4\}\}}
=\sum_{i_1,i_2,i_3\text{ distinct}\atop j_1< j_2}
\left\langle a_{i_1}a\,_{i_3}\,a_{i_1}\,a_{i_2}\atop
       {\bf b}_{j_1}{\bf b}_{j_1}{\bf b}_{j_1}{\bf b}_{j_2} \right\rangle
\end{equation}

\begin{theorem}
~

\begin{itemize}
\item $\SMSym$ is a co-commutative Hopf subalgebra of $\SMCSym$.
\item $\SMSym$ is isomorphic as an algebra to
${\rm End}_{gr}\WSym=\bigoplus \WSym_n\otimes \WSym^*_n$.
\item $\SMSym$ is isomorphic to the quotient of $\SMRSym$ by the ideal
generated by the polynomials $\SMR_{\pi_1,\Pi_2}-\SMR_{\pi_1,\Pi'_2}$
with ${\rm sp}(\Pi_2)={\rm sp}(\Pi'_2)$.
\end{itemize}
\end{theorem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Hopf algebras of packed integer matrices}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Matrix quasi-symmetric functions}

Let $SA$ be the set of packed set matrices such that if one reads the entries
by columns from top to bottom and from left to right, then one obtains the
numbers $1$ to $n$ in the usual order.

\begin{figure}[ht]
\begin{equation}
{\left(\begin{array}{cc}
  \st\{1,2\}&\st\es\\\st\es&\st\{4\}\\\st\{3\}&\st\es\end{array}\right)}
\qquad\qquad
{\left(\begin{array}{cc}
  \st\{1,3\}&\st\es\\\st\es&\st\{4\}\\\st\{2\}&\st\es\end{array}\right)}
\end{equation}
\caption{\label{SA}An element of $SA$ and an element not in $SA$.}
\end{figure}

Let us consider the subalgebra $\MQSym'$ of $\SMQSym$ generated by the
elements of $SA$.

For example,
\begin{equation}
\MQ_{\mccc{2&\k8 0&\k8 1\\0&\k8 3&\k8 4}} = \sum_{i_1<i_2\atop
j_1<j_2<j_3}
 \left\langle a_{i_1}\,a_{i_1}\,a_{i_1}\,a_{i_2}\,a_{i_2}\,a_{i_2}\,a_{i_2}\,a_{i_2}\,
a_{i_2}\,a_{i_2} \atop  {\bf b}_{j_1}{\bf b}_{j_1}{\bf b}_{j_3}{\bf
b}_{j_2}{\bf b}_{j_2} {\bf b}_{j_2}{\bf b}_{j_3}{\bf b}_{j_3}{\bf
b}_{j_3}{\bf b}_{j_3}\right\rangle
\end{equation}


\begin{theorem}
$\MQSym'$ is isomorphic as a Hopf algebra to $\MQSym$.
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Matrix half-symmetric functions}

We reproduce the same construction as for set packed matrices. We
define three algebras $\MRSym$ (resp. $\MCSym$, $\MSym$) of
packed matrices up to a permutation of rows (resp. of
columns, resp. of rows and columns).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{The Hopf algebra $\MRSym$}

Let $\MRSym$ be the subalgebra of $\MQSym$ generated by the polynomials
\begin{equation}
\MR_A:=\sum\MQ_{B}
\end{equation}
%
where $B$ is obtained from $A$ by any permutation of its rows. As for
$\SMRSym$, the realization of $\MRSym$ on bi-words is automatic.
For example,

\begin{equation}
\MR_{\mccc{2&\k8 1&\k8 0\\0&\k8 3&\k8 4}}= \MQ_{\mccc{2&\k8 1&\k8
0\\0&\k8 3&\k8 4}} + \MQ_{\mccc{0&\k8 3&\k8 4\\2&\k8 1&\k8
0}}=\displaystyle\sum_{i_1\neq i_2\atop j_1<j_2<j_3}
\left\langle a_{i_1}\,a_{i_1}\,a_{i_1}\,a_{i_2}\,a_{i_2}\,a_{i_2}\,a_{i_2}\,a_{i_2}\,
a_{i_2}\,a_{i_2} \atop  {\bf b}_{j_1}{\bf b}_{j_1}{\bf b}_{j_3}{\bf
b}_{j_2}{\bf b}_{j_2} {\bf b}_{j_2}{\bf b}_{j_3}{\bf b}_{j_3}{\bf
b}_{j_3}{\bf b}_{j_3}\right\rangle.
\end{equation}

\begin{theorem}
~

\begin{enumerate}
\item $\MRSym$ is a co-commutative Hopf subalgebra of $\MQSym$,
\item $\MRSym$ is also the subalgebra of $\SMRSym$ generated by the
elements $\SMR_A$ where $A$ is any matrix such that each element of the set
composition of its columns is an interval of $[1,n]$.
%\item In terms of the realization, it amounts to take the commutative image of
%all bi-words.
\end{enumerate}
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{The Hopf algebra $\MCSym$}

We construct the algebra $\MCSym$ as the quotient of $\MQSym$ by the
ideal generated by the polynomials ${\rm \MQ}_A-{\rm \MQ}_B$ where
$B$ can be obtained from $A$ by a permutation of its columns.

\begin{theorem}
~

\begin{enumerate}
\item $\MCSym$ is a commutative Hopf algebra,
\item $\MCSym$ is isomorphic as a Hopf algebra to the subalgebra of $\SMCSym$
generated by the elements $\SMC_A$, such that each element of the set
partition of its columns is an interval of $[1,n]$.
\end{enumerate}
\end{theorem}


\def\PMuR{{\rm PMuR}}
\def\MuR{{\rm MuR}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Dimensions of $\MRSym$ and $\MCSym$}

The dimension of the homogeneous component of degree $n$ of $\MRSym$
or $\MCSym$ is equal to the number of packed matrices such that the
sum of the entries is equal to $n$, up a permutation of the rows.

Let us denote by $\PMuR(p,q,n)$ the number of such $p\times q$
matrices. One has obviously
\begin{equation}\label{dimMR1}
\dim \MRSym_n=\sum_{1\leq p,q\leq n}\PMuR(p,q,n).
\end{equation}
The integers   $\PMuR(p,q,n)$ can be computed through the induction
\begin{equation}
 \PMuR(p,q,n)=\MuR(p,q,n)-\sum_{1\leq k,l\leq
 p,q}\left(q\atop l\right)\PMuR(k,l,n),
\end{equation}
where $\MuR(p,q,n)$ is the number of $p\times q$ matrices up to a
permutations of the rows with the sums of the entries equal to $n$.

 Solving this induction and substituting it in equation (\ref{dimMR1}),
   one gets
 \begin{equation}
\dim \MRSym_n=\sum_{i=1}^{n+1}(-1)^{n-i}T_{n+1,i+1}\MuR(n,i,n),
 \end{equation}
where $T_{n,k}=\sum_{j=0}^{n-k}(-1)^{n-k-j}\left(j+k-1\atop
j\right)$ is known as the number of minimal covers of an unlabeled
$n$-set that cover k points of that set uniquely (see sequence A056885
of \cite{Slo}). The generating series of the $T_{n,k}$ is
\[\sum_{i,j}T_{i,j}x^iy^j={\frac {1-x}{\left (1+x\right )\left (1-x-xy\right )}}.\]
%$T_{n,k}=\sum_{j=0}^{n-k}(-1)^{n-k-j}\left(j+k-1\atop
%j\right)$.
The integer $\MuR(n,i,n)$, computed via the  P\'olya enumeration
theorem, is the coefficient of $x^n$ in the cycle index
$Z(G_{n,i})$, evaluated over the alphabet $1+x+\cdots+x^n+\cdots$,
of the subgroup $G_{n_,i}$ of $\S_{in}$ generated by the
permutations $\sigma. \sigma[n]. \sigma[2n].\ \cdots\ . \sigma[in]$
for $\sigma\in \S_n$ (here $.$ denotes the concatenation).

This coefficient is also the number of partitions $N_{n,i}$ of $n$
objects with $i$ colors whose generating series is
$$\sum_{n}N_{n,i}x^n=\prod_k\left(1\over 1-x^k\right)^{\left(i+k\atop
i\right)}.$$

Hence
\begin{proposition}
 \begin{equation}
\dim \MRSym_n=\sum_{i=1}^{n+1}(-1)^{n-i}T_{n+1,i+1}N_{n,i}.
 \end{equation}
\end{proposition}

The first values are
\begin{equation}
\begin{split}
{\rm Hilb}(\MRSym)={\rm
Hilb}(\MCSym)=&
\; 1+t+4t^2+16t^3+76t^4+400t^5+2356t^6+15200t^7+106644t^8\\
&+ 806320t^9+6526580t^{10}+\cdots
\end{split}
\end{equation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Matrix symmetric functions}

The algebra $\MSym$ of \emph{matrix symmetric functions} is the subalgebra of
$\MCSym$ generated by

\begin{equation}
\sum_{\sigma\in\S_n}\MR_{B},
\end{equation}
where $B$ is obtained from $A$ by any permutation of its rows.

\begin{theorem}
~

\begin{enumerate}
\item $\MSym$ is a commutative and co-commutative Hopf subalgebra of
$\MCSym$.
%
\item $\MSym$ is isomorphic as a Hopf algebra to the subalgebra of $\SMSym$
generated by the elements $\SM_A$, such that each element of the set
partition of its columns is an interval of $[1,n]$.
%
\item $\MSym$ is isomorphic to the quotient of $\MRSym$ by the ideal generated
by the polynomials ${\rm \MR}_A-{\rm \MR}_B$ where $B$ can be obtained from
$A$ by a permutation of its columns.
\end{enumerate}
\end{theorem}

The following diagram commutes

\begin{equation*}
\newdir{ >}{{}*!/-4mm/@{>}}
\xymatrix@R=10mm@L=10mm{& \SMQSym \ar@{<-<}[dl] \ar@{->>}[ddr]\ar@{<-<}[rrr]&&&\MQSym\ar@{<-<}[dl] \ar@{->>}[ddr]\\
\SMRSym\ar@{->>}[ddr]\ar@{<-<}[rrr]& &&\MRSym\ar@{->>}[ddr]\\
&&\SMCSym\ar@{<-<}[dl]\ar@{<-<}[rrr]&&&\MCSym\ar@{<-<}[dl]\\
  &\SMSym\ar@{<-<}[rrr]&&&\MSym}
\end{equation*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Dendriform structures over $\SMQSym$}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tridendriform structure}

One defines three product rules over bi-words as follows:
\begin{enumerate}
\item
$\left\langle u_1\atop v_1\right\rangle \prec
 \left\langle u_2\atop v_2\right\rangle
=\left\langle u_1\atop v_1\right\rangle \star
 \left\langle u_2\atop v_2\right\rangle
 \mbox{\ \ if $\max(u_1)>\max(u_2)$,\ and $0$ otherwise.}$
\item
$\left\langle u_1\atop v_1\right\rangle \,\,\circ\,\,
 \left\langle u_2\atop v_2\right\rangle
=\left\langle u_1\atop v_1\right\rangle \star
 \left\langle u_2\atop v_2\right\rangle
 \mbox{\ \ if $\max(u_1)=\max(u_2)$,\ and $0$ otherwise.}$
\item
$\left\langle u_1\atop v_1\right\rangle \succ
 \left\langle u_2\atop v_2\right\rangle
=\left\langle u_1\atop v_1\right\rangle \star
 \left\langle u_2\atop v_2\right\rangle
 \mbox{\ \ if $\max(u_1)<\max(u_2)$,\ and $0$ otherwise.}$
\end{enumerate}

\begin{proposition}
The algebra of bi-words endowed with the three product rules $\prec, \circ$,
and $\succ$ is a tridendriform algebra.

Moreover, $\SMQSym$ is stable by those three rules. So it
is a tridendriform algebra.
\end{proposition}

More precisely, one has:
\begin{enumerate}
\item $\SMQ_{\left\langle u\atop\bf v\right\rangle}\prec\SMQ_{\left\langle u'\atop\bf v'\right\rangle}
=\displaystyle\sum_{w=x.y\in u\star_W u'\atop |x|=|u|;\
\max(y)<\max(x)}\SMQ_{\left\langle w\atop {\bf v}{\bf
v'}[\max(v)]\right\rangle}$
\item $\SMQ_{\left\langle u\atop\bf v\right\rangle}\circ\SMQ_{\left\langle u'\atop\bf v'\right\rangle}
=\displaystyle\sum_{w=x.y\in u\star_W u'\atop |x|=|u|;\
\max(y)=\max(x)}\SMQ_{\left\langle w\atop {\bf v}{\bf
v'}[\max(v)]\right\rangle}$
\item $\SMQ_{\left\langle u\atop\bf v\right\rangle}\succ\SMQ_{\left\langle u'\atop\bf v'\right\rangle}
=\displaystyle\sum_{w=x.y\in u\star_W u'\atop |x|=|u|;\
\max(y)>\max(x)}\SMQ_{\left\langle w\atop {\bf v}{\bf
v'}[\max(v)]\right\rangle}$.
\end{enumerate}

\begin{corollary}
$\SMCSym$, $\MQSym$ and $\MCSym$ are tridendriform.
\end{corollary}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Bidendriform structures}

%As for words, there does not exist a structure of Hopf algebra
Let us define two product rules $\ll=\prec$ and $\gg=\circ+\succ$ on bi-words.
We now split the non-trivial parts of the coproduct of the $\SMQ$ of
$\SMQSym$, as
\begin{enumerate}
\item
$\Delta_\ll(\SMQ_{A})=
\displaystyle\sum_{A=\left(B\atop C\right),\ A\neq B,C\atop \max(B)=\max(A)}
 \SMQ_{\std(B)}\otimes \SMQ_{\std(C)}.$
\item
$\Delta_\gg(\SMQ_{A})=
\displaystyle\sum_{A=\left(B\atop C\right),\ A\neq B,C\atop \max(C)=\max(A)}
 \SMQ_{\std(B)}\otimes \SMQ_{\std(C)}.$
\end{enumerate}

\begin{theorem}
$\SMQSym$ is a bidendriform bialgebra.
\end{theorem}

Recall that $\SMCSym$ is the quotient of $\SMQSym$ by the ideal generated by
$\SMQ_A - \SMQ_B$ where $A$ and $B$ are the same matrices up to a permutation
of their columns, the row containing the maximal element is the same for any
element of a given class, so that the left coproduct and the right coproduct
are compatible with the quotient.
Moreover, the left and right coproduct are internal within $\MQSym$, so that

\begin{corollary}
$\SMCSym$ and $\MQSym$ are bidendriform sub-bialgebras of $\SMQSym$.
\end{corollary}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{bi-words realization of $LDiag(q_c,q_s)$}
% and $Diag$}

Let us define a two-parameter generalization of $\MQSym$. For this purpose,
consider bi-words with parameter-commuting bi-letters depending on the
biletters as follows:

\begin{equation}
\begin{split}
\left\langle y x \atop z t \right\rangle
=q_c \left\langle x y \atop t z \right\rangle
&\mbox{ if }y>x, \\
\left\langle x x \atop z t \right\rangle
=q_s \left\langle x x \atop t z \right\rangle
&\mbox{ if }z<t.\\
\end{split}
\end{equation}

Let us now define the realization as a sum of bi-words of a packed integer
matrix with $p$ rows and $q$ columns:
\begin{equation}
{\bf LD}_M := \sum_{i_1<\dots<i_p \atop j_1<\dots<j_q}
     \prod_{a=1}^n \prod_{b=p}^1
     \left\langle i_a\atop j_b \right\rangle^{M_{ij}}.
\end{equation}

For example,
\begin{equation}
{\bf LD}_{\mcc{3&\k8 5\\1&\k8  3}} := \sum_{i_1<i_2\atop j_1<j_2}
\left\langle i_1^5\,i_1^3\,i_2^3\,i_2\atop j_2^5\,j_1^3\,j_2^3\,j_1
\right\rangle.
\end{equation}


We then have
\begin{theorem}
~

\begin{itemize}
\item The $\bf LD$ generate an algebra,
%\footnote{AFAIRE : Hopf pour quel coproduit ???}
%\item Given two $q
\item The specialization $q_s=q_c=1$ gives back $\MQSym$.
\end{itemize}
\end{theorem}


For example, one has:
\begin{equation}
{\bf LD}_{\mccc{
        2 &\k8 0 \\
        1 &\k8 4}}
\star {\bf LD}_{\left(1\right)} = {\bf LD}_{\mccc{
        2 &\k8 0 &\k8 0 \\
        1 &\k8 4 &\k8 0 \\
        0 &\k8 0 &\k8 1 }}
+ q_s^5\, {\bf LD}_{\mccc{
                  2 &\k8 0 &\k8 0 \\
                  1 &\k8 4 &\k8 1 }}
+ q_c^5\, {\bf LD}_{\mccc{
                  2 &\k8 0 &\k8 0 \\
                  0 &\k8 0 &\k8 1 \\
                  1 &\k8 4 &\k8 0}}
+ q_c^5q_s^2\, {\bf LD}_{\mccc{
                      2 &\k8 0 &\k8 1 \\
                      1 &\k8 4 &\k8 0}}
+ q_c^7\, {\bf LD}_{\mccc{
                  0 &\k8 0 &\k8 1 \\
                  2 &\k8 0 &\k8 0 \\
                  1 &\k8 4 &\k8 0 }}
\end{equation}



since
\begin{equation}
\begin{split}
\sum_{i_1<i_2 \atop j_1<j_2}
\left\langle i_1\,i_1\,i_2\,i_2\,i_2\,i_2\,i_2 \atop j_1j_1j_2j_2j_2j_2j_1
\right\rangle
\star \sum \left\langle i \atop j \right\rangle
= &
\sum_{i_1<i_2<i_3 \atop j_1<j_2<j_3}
   \left\langle i_1^2\,i_2^4\, i_2\, i_3 \atop j_1^2j_2^4j_1j_3\right\rangle
+
\sum_{i_1<i_2(=i_3) \atop j_1<j_2<j_3}
   q_s^5\left\langle i_1^2\,i_2\,i_2^4i_2 \atop
j_1^2j_3j_2^4j_1\right\rangle
+
\sum_{i_1<i_3<i_2 \atop j_1<j_2<j_3}
   q_c^5\left\langle i_1^2\,i_3\,i_2^4\,i_2 \atop j_1^2j_3j_2^4j_1
   \right\rangle\\
&+
\sum_{i_1(=i_3)<i_2 \atop j_1<j_2<j_3}
  q_s^2q_c^5\left\langle i_1\,i_1^2\,i_2^4\,i_2 \atop j_3j_1^2j_2^4j_1
            \right\rangle
+
\sum_{i_3<i_1<i_2 \atop j_1<j_2<j_3}
 q_c^7\left\langle i_3\,i_1^2\,i_2^4\,i_2 \atop j_3j_1^2j_2^4j_1\right\rangle.
\end{split}
\end{equation}

%\medskip
%We now turn to a bi-word realization of DIAG. To that purpose, we
%design a multiplicative basis of \textbf{MSym} such that
% \begin{equation}
%\phi_A=M_{A_1}\cdots M_{A_n}
% \end{equation}
% if $A=\left(\begin{array}{ccc}
%   A_1&&0\\
%   &\ddots&\\
%   0&&A_n
%  \end{array}\right)$ with $n$ maximal.
%\begin{equation}
%\phi_C = \left\{\begin{array}{ll}
%                M_C  & \mbox{if }C\mbox{ cannot be decomposed into diagonal blocks} \\
%                M_A\,M_B & \mbox{if }\displaystyle{C=\left(\begin{array}{cc} A & 0 \\
%                                                                             0 & B\end{array}\right) }\end{array}\right.
%\end{equation}
%
%\footnote{AFAIRE : a completer.}
