% EJC papers must begin as follows
\documentclass[12pt]{article}
\usepackage{e-jc}

% only use standard LaTeX packages
% only include essential packages

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; i.e. there must be no text protruding into the margins
% use \sloppy to avoid overly wide text
\sloppy

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Self-dual interval orders and row-Fishburn matrices}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Sherry H. F. Yan\thanks{Supported by  the National Natural Science Foundation of China (No. 10901141), Zhejiang Innovation Project(Grant No. T200905) and Opening Fund of Top Key Discipline of Computer Software and Theory in Zhejiang Provincial Colleges at Zhejiang Normal University.   }\\
\small Department of Mathematics  \\[-0.8ex]
\small Zhejiang Normal University\\[-0.8ex]
\small Jinhua 321004, P.R. China\\
\small\tt huifangyan@hotmail.com\\
\and
  Yuexiao  Xu \\
\small Department of Mathematics  \\[-0.8ex]
\small Zhejiang Normal University\\[-0.8ex]
\small Jinhua 321004, P.R. China\\
\small\tt  xyx1985@163.com
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Nov 18, 2011}{Mar 29, 2012}\\
\small Mathematics Subject Classifications: 05A05,
05C30}

\begin{document}
%\includegraphics[width=\textwidth]{pageHeader}
\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
Recently, Jel\'{i}nek derived  that the number of self-dual interval orders of reduced size $n$ is twice the number of row-Fishburn matrices of size $n$ by using generating functions. In this paper, we present a bijective proof of this
relation by establishing a  bijection  between two variations of
upper-triangular matrices  of nonnegative integers.   Using the
bijection, we provide a combinatorial proof  of the refined
relations between self-dual Fishburn matrices and row-Fishburn matrices in answer to a problem proposed by  Jel\'{i}nek.

% keywords are optional
\bigskip\noindent \textbf{Keywords:} self-dual interval order;  self-dual
Fishburn matrix; row-Fishburn matrix.
\end{abstract}

\section{Introduction}
A  poset is said to be  an  {\em interval order}  ( also known as
$(2+2)$-free poset) if it does not contain an induced subposet that
is isomorphic to $2+2$, the union of two disjoint $2$-element
chains. Let $P$ be a poset with a strict order relation  $\prec$.  A
{\em strict down-set} of an element $x \in P$ is the set $D(x)$ of
all the elements of P that are smaller than $x$, i.e., $D(x) = \{y
\in  P: y \prec x\}$. Similarly, the {\em strict up-set} of $x$,
denoted by $U(x)$, is the set $\{y \in P: y\succ x\}$. A poset $P$
is $(2+2)$-free if and only if its sets of strict down-sets,
$D(P)=\{D(x): x\in P\}$ can be
 written as
  $$
  D(P)=\{D_1, D_2, \ldots, D_m \}
 $$
where $\emptyset=D_1\subset D_2\subset\ldots \subset D_m$, see
\cite{Bog, melon}. In such context, we say that $x\in P$ has {\em
level} $i$ if $D(x)=D_i$. An element has level 1 if and only if  it is minimal.
   Following Fishburn
\cite{fish1}, we call the number $m$ of distinct strict down-sets
the {\em magnitude} of P. It turns out that $m$ is also equal to the
number of distinct strict up-sets, and we can order the strict
up-sets of $P$ into a decreasing chain
$$
  D(P)=\{U_1, U_2, \ldots, U_m \}
 $$
where $ U_1\supset U_2\supset\ldots \supset U_m=\emptyset$, see
\cite{fish1, fish2}. We say that $x$ has up-level $i$ if $U(x) =
U_i$. An element has up-level $m$ if and only if  it is maximal. 


The {\em dual} of a poset $P$ is the poset $\overline{P}$ with the
same elements as $P$ and an order relation  $\overline{  \prec}$
defined by $x\overline{  \prec} y$ $\Longleftrightarrow$ $y\prec x$.
A poset is {\em self-dual} if it is isomorphic to its dual.




Fishburn \cite{fish1, fish3} did pioneering work on interval orders;
for instance, he   provided several equivalent
characterizations of interval orders and  established
a bijection between interval orders and a certain kind of integer
matrices, called Fishburn matrices. Recently, Bousquet-M\'elou et
al. \cite{melon} constructed bijections between interval orders and
ascent sequences, between ascent sequences and permutations avoiding
a certain pattern, between interval orders and regular linearized
chord diagrams by Stoimenow \cite{Stoi}.  Several other papers have
focused on bijections between interval orders and other objects. For
instance, Dukes and Parviainen \cite{Duck} have described a direct
bijection between Fishburn matrices and ascent sequences, while the
papers of Claesson et al. \cite{cla1} and Dukes et al. \cite{Duck3}
extend the bijection between interval orders and Fishburn matrices
to more general combinatorial structures.


 A {\em Fishburn} matrix of
size $n$ is an upper-triangular matrix with nonnegative integers
which sum to $n$ and  each row and each column contains a nonzero
entry.   Throughout this paper we assume that  each matrix has its rows
numbered from top to bottom, and columns numbered left-to-right,
starting with row and column number one. We let $M_{i,j}$ denote the
entry of M in row $i$ and column $j$.  The {\em size} of a matrix
$M$ is the sum of all its entries. Moreover, the {\em dimension} of
an upper triangular matrix is defined to the number of rows.


The {\em dual} matrix of $M$, denoted by $\overline{M}$, is obtained
from $M$ by transposition along the diagonal running from
bottom-left to top-right. More precisely,  for $1\leq i,j\leq m$, we
have $\overline{M}_{i,j}=M_{m+1-j,m+1-i}$ where $m$ is the dimension
of $M$. If a matrix M is equal to $\overline{M}$, we call it {\em
self-dual}.



Fishburn \cite{fish1, fish3} showed that an interval order $P$ of
magnitude m corresponds to an $m\times m$ Fishburn matrix $M$ with
$M_{i,j}$ being equal to the number of elements of $P$ that have
level $i$ and up-level $j$. Jel\'{i}nek \cite{jel} showed that the
Fishburn's bijection turns out to be    a bijection between
self-dual interval orders of size $n$ and self-dual Fishburn
matrices of size $n$.

Following the terminologies given in  \cite{jel},   we distinguish
three types of cells in a Fishburn matrix $M$ of dimension $k$ : a
cell $(i, j)$ is a diagonal cell if $i+j = k+1$, i.e., $(i, j)$
belongs to the north-east diagonal of the matrix. If $i+j < k +1$
(i.e., $(i, j)$ is above and to the left of the diagonal) then $(i,
j) $ is a North-West cell, or NW-cell, while if $i + j > k + 1$,
then $(i, j)$ is an SE-cell. Clearly, NW-cells and diagonal cells
together determine a self-dual Fishburn matrix. The {\em reduced
size} of a self-dual fishburn matrix $M$ is the sum of all diagonal
cells and NW-cells. The {\em reduced size} of a self-dual interval
order $P$ is the reduced size of its corresponding self-dual
Fishburn matrix under Fishburn's bijection.





 A {\em row-Fishburn} matrix of size $n$
is defined to be an upper-triangular matrix with nonnegative
integers which sum to $n$ and each row contains a nonzero entry.
   In a matrix $A$, the {sum} of a column (resp. row) is
defined to the sum of all the entries in this column (resp. row). A
column or a row is said to be {\em zero} if it contains no nonzero
entries.   The  set of self-dual Fishburn matrices of reduced size
$n$ is denoted by $\mathcal{M}(n)$. Let $\mathcal{ M}(n,k,p)$
be the set of self-dual Fishburn matrices of reduced size $n$ whose
first row has sum $k$ and diagonal cells have sum $p$.    Let
$\mathcal{RM}(n)$   be the set of row-Fishburn matrices of size $n$.
The set of row-Fishburn matrices in $\mathcal{RM}(n)$ whose last
column has sum $k$ is denoted by $\mathcal{RM}(n,k)$. Let
$\mathcal{RM}(n,k,p)$ denote  the set of row-Fishburn matrices in
$\mathcal{RM}(n,k)$  whose    first row has sum $p$. Moreover, the
set of self-dual interval orders of reduced size $n$ is denoted by
$\mathcal{I}(n)$.

Based on the bijection between interval orders and Fishburn
matrices, Jel\'{i}nek \cite{jel} presented a new method to derive
formulas for the generating functions of interval orders, counted
with respect to their size, magnitude, and number of minimal and
maximal elements, which generalize previous results on refined
enumeration of   interval orders obtained by Bousquet-M\'elou et al.
\cite{melon}, Kitaev and Remmel \cite{Kitaev}, and Dukes et al.
\cite{Duck2}. Applying the new method, Jel\'{i}nek \cite{jel}
obtained formulas for the generating functions of  self-dual
interval orders with respect to analogous statistics.  From the
obtained  generating functions,   relations between self-dual
Fishburn matrices  and row-Fishburn matrices were derived, that is,
\begin{equation}\label{eq1}
|\mathcal{M}(n, k, 0)|=  |\mathcal{RM}(n,k)|,
\end{equation}
 and for $p\geq 1$
\begin{equation}\label{eq2}
|\mathcal{M}(n,k,p)|=  |\mathcal{RM}(n,k,p)|.
\end{equation}
Combining   the bijection between self-dual interval orders  and
self-dual Fishburn martices,  formulas (\ref{eq1}) and (\ref{eq2}),
Jel\'{i}nek derived that for $n\geq 1$,
\begin{equation}\label{eq3}
|\mathcal{I}(n)|=|\mathcal{M}(n)|=  2|\mathcal{RM}(n)|,
\end{equation}
and asked for  bijective proofs  of  (\ref{eq1}) and (\ref{eq2}).
The main objective  of this paper is to present    bijective proofs
of these formulas by establishing a one-to-one correspondence
between two variations of upper-triangular matrices  of nonnegative
integers.

Let $\mathcal{M}(n,k)$ be the set of self-dual Fishburn matrices of
reduced size $n$ whose first row has sum $k$. Denote by
$\mathcal{EM}(n,k)$ (resp. $\mathcal{OM}(n,k)$ ) the set of
self-dual Fishburn matrices in $\mathcal{M}(n,k)$ whose dimension
are even (resp. odd). Using the bijection between two variations of
upper-triangular matrices  of nonnegative integers, we derive that
\begin{equation}\label{eq8}
|\mathcal{EM}(n,k)|=|\mathcal{OM}(n,k)|=|\mathcal{RM}(n,k)|.
\end{equation}




\section{The bijective proofs}
Recall that a self-dual Fishburn matrix is determined by its
NW-cells and diagonal cells. Given   a self-dual Fishburn matrix
$M$,
  the {\em reduced matrix} of $M$, denoted by $R(M)$,  is a matrix
obtained from $M$ by filling all the SE-cells with zeros. An
upper-triangular matrix is said to be a {\em super } triangular matrix
if all  its SE-cells are zero.

\begin{lemma}\label{le}
Let   $M'$ be a   super triangular matrix  of dimension $m$.  Then
$M'$ is a reduced matrix of a self-dual Fishburn matrix  if and only
if it satisfies the following two conditions:
\begin{itemize}
\item[(i)]for $1\leq i\leq \lceil{m\over 2}\rceil$, each column $i$ contains
a
nonzero entry;

\item[(ii)] for $1\leq i\leq \lceil{m\over 2}\rceil$,  either row $i$ or column $m+1-i$
contains a nonzero entry.
\end{itemize}
\end{lemma}
\begin{proof}  Let $M$ be a self-dual Fishburn matrix with $R(M)=M'$. Clearly,
$M'$ is a super triangular matrix. Since the first $\lceil{m\over
2}\rceil$ columns of $M'$ are the same as those in $M$, the
condition $(i)$  follows immediately. It remains to show that $M'$
satisfies condition  $(ii)$.  Since $M$ is self-dual Fishburn
matrix, for all $1\leq i\leq m$,
  row $i$ must contains  a nonzero entry,   that is, $$\sum_{j=1}^{m}
M_{i,j}=\sum_{j=1}^{m-i}
M_{i,j}+\sum_{j=m+1-i}^{m}M_{i,j}=\sum_{j=1}^{m-i}
M_{i,j}+\sum_{j=1}^{i}M_{j,m+1-i}> 0.$$  Hence, for $1\leq i\leq
\lceil{m\over 2}\rceil$,  either row $i$ or column $m+1-i$  of
$R(M)$ contains a nonzero entry.    Therefore,  the condition $(ii)$
holds for $R(M)$.




Conversely, given a   super triangular matrix $M'$  satisfying
conditions $(i)$ and $(ii)$,  We can recover a self-dual matrix $M$
from $M'$ by filling the SE-cell $(m+1-j, m+1-i)$  with $M'_{i,j}$.
      If $1\leq i\leq \lceil{m\over 2}\rceil$, the
sum of row $i$ of $M$ is given by
$$ \sum_{j=i}^{m}
M_{i,j}=\sum_{j=i}^{m-i}
M_{i,j}+\sum_{j=m+1-i}^{m}M_{i,j}=\sum_{j=1}^{m-i}
M_{i,j}+\sum_{j=1}^{i}M_{j,m+1-i}=\sum_{j=1}^{m-i}
M'_{i,j}+\sum_{j=1}^{i}M'_{j,m+1-i}. $$ By   the    condition
$(ii)$, we have $\sum_{j=i}^{m} M_{i,j}=\sum_{j=1}^{m-i}
M'_{i,j}+\sum_{j=1}^{i}M'_{j,m+1-i}>0$, which implies that row $i$
contains a nonzero entry. If $\lceil{m\over 2}\rceil+1\leq i\leq m$,
the sum of row $i$ of $M$ is given by
$$
\sum_{j=i}^{m} M_{i,j}=
\sum_{j=i}^{m}M'_{m+1-j,m+1-i}=\sum_{j=1}^{m+1-i}M'_{j,m+1-i},
$$
which implies that the sum of row $i$ of $M$ is the same as that of
column $m+1-i$ of $M'$. By condition $(i)$, row $i$ contains a
nonzero entry. Hence $M$ is a self-dual Fishburn matrix with
$R(M)=M'$. This completes the proof.
\end{proof}
 Denote by $\mathcal{SM}_k(n)$ the set of all
super triangular matrices   of size $n$  and dimension $2k+1$ having
the following two properties:
\begin{enumerate}
\item[$(a)$]    for $1\leq i\leq k$, each column $i$ contains a
nonzero entry;
 \item[$(b)$] for $1\leq i\leq k$,  either row $ k+1-i$ or
column $k+1+i$ contains a nonzero entry.
\end{enumerate}
 Let $\mathcal{SM}(n)=\bigcup_{k\geq 0}\mathcal{SM}_k(n)$.










Now we proceed to present a map $\alpha$ from $\mathcal{M}(n)$ to
$\mathcal{SM}(n)$.
 Given a  nonempty self-dual
matrix $M$ of dimension $m$,    let $\alpha(M)$  be the matrix
obtained from $M$ by the following procedure.
\begin{itemize}
\item  If $m=2k+1$ for some integer $k\geq 0$, then let $\alpha(M)$ be the
matrix obtained from the reduced matrix  $R(M)$  of $M$ by
interchanging the cell $(i,k+1)$ and the diagonal  cell $(i, m+1-i)$
for $1\leq i\leq k$.
\item If $m=2k$ for some integer $k\geq 1$, then let $A$ be the matrix
obtained from $R(M)$ by adding one zero row and one zero column
immediately after column $k$ and row $k$. Define $\alpha(M)$ to be
the matrix obtained from $A$ by interchanging the cell $(i,k+1)$ and
the diagonal  cell $(i, m+1-i)$ of the resulting matrix $A$.
\end{itemize}

Obviously,  $\alpha(M)$ is a super triangular matrix of dimension
$2k+1$ and  size $n$. It easy to check that the map $\alpha$
preserves the first $k$ columns and  the total  sum of
  row $i$ and column $m+1-i$ of the reduced matrix $R(M)$.   By Lemma \ref{le},
  the matrix $\alpha(M)$ has properties $(a)$ and $(b)$.  Hence $\alpha(M)$ is a
super triangular matrix in $\mathcal{SM}(n)$.



Conversely,  given a     super  triangular   matrix $M'$ in
$\mathcal{SM}(n)$ of dimension $2k+1$, we can recover a matrix $M\in
\mathcal{M}(n)$ with $\alpha(M)=M'$. First we   interchange  the
cell $(i,k+1)$ with the diagonal cell $(i, m-i)$ for $1\leq i\leq
k$. Then we obtain a matrix $A$ by  deleting  column $k+1$ and row
$k+1$ if they are zero.  It is easy to check that properties $(a)$
and $(b)$ ensure  that the obtained matrix $A$ is the reduced matrix
of a self-dual Fishburn matrix. Let $M$ be a self-dual Fishburn
matrix with $R(M)=A$. Hence $\alpha$ is a bijection between
$\mathcal{M}(n)$ and $\mathcal{SM}(n)$.







Let $M$ be a super   triangular matrix of dimension $2k+1$, then
column $k+1$ is called a {\em center} column.  From the construction
of the bijection $\alpha$, we see that the map $\alpha$ transforms
the sum of  the diagonal cells of a self-dual matrix to the sum of
the center column of a super triangular matrix. Hence, we have the
following result.

\begin{theorem}\label{th1}
The map $\alpha$ is a bijection between $\mathcal{M}(n)$ and
$\mathcal{SM}(n)$. Moreover, the  bijection $\alpha$  preserves the
sum of the first row, and transforms the sum of  the diagonal cells
of a self-dual matrix to the sum of the center column of a super
triangular matrix.
\end{theorem}

\begin{example}
Consider a matrix $A\in \mathcal{M}(5)$,
$$
A=\begin{bmatrix}
 1 &0  &1&0  &0 \\
0 &1  &1&1  &0 \\
0 &0   &0&1  &1\\
 0 &0  &0 &1  & 0\\
  0 &0   &0&0  & 1\\
\end{bmatrix}.$$
The  reduced matrix of $A$ is given by
$$
R(A)=\begin{bmatrix}
 1 &0  &1&0  &0 \\
0 &1  &1&1  &0 \\
0 &0   &0&0  & 0\\
 0 &0  &0 &0  & 0\\
  0 &0   &0&0  & 0\\
\end{bmatrix},$$

and we have

$$
\alpha(A)=\begin{bmatrix}
1 &0  &0 &0  &1\\
0 &1  &1 &1  & 0\\
 0 &0  &0 &0  & 0\\
 0 &0  &0 &0  & 0\\
  0 &0 &0  &0  & 0\\
\end{bmatrix}.$$

\end{example}












Let $\mathcal{B}(n)$ the set of upper-triangular matrices of size
$n$ in which each row contains a nonzero entry except for the first
row.   Given  a nonempty matrix $A\in \mathcal{RM}(n)$, we can get
two distinct matrices in $\mathcal{B}(n)$  from $A$ by either doing
nothing or adding a zero row  and a zero column before the first row
and the first column.  Thus for $n\geq 1$ we have the following
relation
\begin{equation}\label{eq4}
 |\mathcal{B}(n)|=2|\mathcal{RM}(n)|.
\end{equation}
Now we proceed to  construct a bijection between the set
$\mathcal{SM}(n)$ and the set $\mathcal{B}(n)$. Before constructing
the bijection, we need some definitions. In  a matrix $A$  with $m$
rows, the operation of adding column $i$ to column  $j$ is defined
by increasing  $A_{k,j}$ by $A_{k,i}$  for each $k=1,2,\ldots, m$.




Let $\mathcal{B}(n,k,p)$ be the set of  matrices in $\mathcal{B}(n)$
whose whose first row has sum $p$ and last column has sum $k$.
Similarly,  let  $\mathcal{SM}(n,k,p)$ be the set of
 matrices in $\mathcal{SM}(n)$ whose first row has sum $k$ and
center column has sum $p$.



 \begin{theorem}\label{th2}
For $n\geq 1$, there is a bijection $\beta$ between  $\mathcal{SM}(n)$  and
$\mathcal{B}(n)$. Moreover, the map $\beta$ is essentially a
bijection between  $\mathcal{SM}(n,k,p)$  and $\mathcal{B}(n,k,p)$.
\end{theorem}
\begin{proof} Given a nonempty triangular  matrix $A\in \mathcal{SM}(n) $ of
dimension $2k+1$, we recursively construct a sequence of super
triangular matrices $A^{(0)}, A^{(1)}, \ldots, A^{(l)}$.  Let
$A^{(0)}=A$ and assume that we have obtained the matrix $A^{(j)}$.
  Let $A^{(j)}$ be a super triangular matrix of dimension $2r+1$
for some integer $r$. For $1\leq i\leq r$, if each column $r+1+i$ is
zero, then let $A^{(l)}=A^{(j)}$. Otherwise, we proceed to generate
the matrix $A^{(j+1)}$ by the following {\em insertion} algorithm.
\begin{itemize}
\item  Find the largest value $i$ such that column $r+1+i$
contains a nonzero entry. Then fill the entries of column  $r+1+i$
with zeros.
\item Insert  one column immediately after column $r+1-i$, one zero
row immediately after row $r+1-i$,  one zero column immediately
before column $r+1+i$ and one zero  row  immediately before row
$r+1+i$. Let the entry in row $j$ of  the new inserted column after
column $r+1-i$ be filled with the entry in row $j$ of  column
$r+1+i$ of $A^{(j)}$ for $1\leq j\leq 2r+1$.
\end{itemize}
   Suppose that $A^{(l)}$ is
of dimension $2q+1$. Then the last $q$ rows and $q$ columns  of
$A^{(l)}$ are zero rows and columns.  Let $B$ be an upper-triangular
matrix obtained from $A^{(l)}$ by deleting the last $q$ columns and
$q$ rows.    From the    above insertion procedure to generate
$A^{(j+1)}$ form $A^{(j)}$ ,  we see that the inserted column after
column $r+1-i$ contains a nonzero entry. This ensures that each
matrix $A^{(j)}$ has property $(a)$ with $0\leq j\leq l$. Hence each
column $i$ of $A^{(l)}$ contains a nonzero entry with $1\leq i\leq
q$. Hence, $B$ is an upper-triangular matrix in which each column
contains a nonzero entry except for the last column. Moreover, the
insertion algorithm preserves the sum of each nonzero row of $A$,
which implies that $B$ is of size $n$.  Let $\beta(A)$ be the dual
matrix of $B$.  Hence we have $\beta(A)\in \mathcal{B}(n)$.



Conversely, we can construct a matrix   $A=\beta'(A')$ in
$\mathcal{SM}(n)$ from a matrix $A'$ of dimension $k+1$ in
$\mathcal{B}(n)$. Let  $B$
  be the dual matrix of $A'$. Define $M$ to be
  a matrix of dimension $2k+1$ obtained from  $B$ by adding $k$ consecutive zero rows and    $k$ consecutive
 zero columns immediately after column $k+1$ and row $k+1$.
Clearly, the obtained matrix is a super  triangular matrix having
property $(a)$. If for all $1\leq i\leq k$, either row $k+1-i$ or
column $k+1+i$ contains a nonzero entry, then we do nothing for $M$
and let $A=M$. Otherwise, we can construct a new super triangular
matrix $A$ by the following {\em removal} algorithm.
\begin{itemize}
\item Find the  least  value $i$ such that neither row $k+1-i$ nor column $k+1+i$ contains a nonzero entry.
Then we obtain a  super   triangular matrix by     adding column
$k+1-i$ to column $k+2+i$ and removing columns $k+1+i$, $k+1-i$ and
rows $k+1-i$, $k+1+i$.
 \item Repeat the above procedure for the resulting matrix until
the obtained matrix has property $(b)$.
\end{itemize}
 Obviously, the obtained matrix $A$ is a super
triangular matrix    having properties  $(a)$ and $(b)$. Since the
algorithm preserves the sums of entries in each non-zero row of $B$,
the matrix $A$ is of size $n$ and the sum of the first row of $A$ is
the same as  that of $B$.   The property  $(b)$ ensures that the
inserted columns in the insertion algorithm are the removed columns
in the removal algorithm. Thus the map $\beta'$ is the inverse of
the map $\beta$.  From the construction of the removal algorithm,
the sum of the center column of $A$ is equal to the sum of the last
column of $B$ as well as the the sum of the first row of $A'$. This
completes the proof.
\end{proof}


\begin{example}
Consider a matrix $A\in \mathcal{SM}(6)$,
$$
A=\begin{bmatrix}
1 &0  &0 &1  &1\\
0 &1  &1 &1  & 0\\
 0 &0  &0 &0  & 0\\
 0 &0  &0 &0  & 0\\
  0 &0 &0  &0  & 0\\
\end{bmatrix}.$$
Let $A^{(0)}=A$. By applying the insertion algorithm, we get


$$A^{(1)}=\begin{bmatrix}
1 &{\textbf   1}&0  &0 &1  &\textbf{0}&0\\
\textbf{0} &\textbf{0}&\textbf{0}  &\textbf{0} &\textbf{0} & \textbf{0} & \textbf{0}\\
0 &\textbf{0}&1  &1 &1  &\textbf{0}& 0\\

 0&\textbf{0} &0  &0 &0  &\textbf{0}& 0\\

 0&\textbf{0} &0  &0 &0 &\textbf{0} & 0\\
 \textbf{0}&\textbf{0} &\textbf{0}  &\textbf{0} &\textbf{0} &\textbf{0} & \textbf{0}\\
  0 &\textbf{0}&0 &0  &0 &\textbf{0} & 0\\

\end{bmatrix},$$

$$A^{(2)}=\begin{bmatrix}
1 & 1 &0 &\textbf{1} &0 &\textbf{0}&0  & 0 &0\\
 0  & 0 & 0 &\textbf{0}  & 0  &\textbf{0}& 0  &  0  &  0 \\
0 & 0 &1 &\textbf{1} &1 &\textbf{0}&0  & 0 & 0\\
\bf{0} & \textbf{0} &\textbf{0} &\textbf{0} &\textbf{0}&\textbf{0} &\textbf{0}  &\textbf{0}& \textbf{0}\\
 0& 0 &0 &\textbf{0} &0 &\textbf{0}&0  & 0 & 0\\
 \textbf{0}& \textbf{0}  &\textbf{0 }&\textbf{0} &\textbf{0} &\textbf{0}&\textbf{0} & \textbf{0}  & \textbf{0}\\

 0& 0  &0 &\textbf{0} &0 &\textbf{0}&0 & 0  & 0\\
  0 & 0  & 0 &\textbf{0}  & 0 &\textbf{0} & 0  & 0 &  0 \\
  0 & 0 &0 &\textbf{0} & 0  & \textbf{0 } &0 & 0  & 0\\

\end{bmatrix},$$
where the inserted rows and columns are illustrated in bold at each
step of the insertion algorithm. Removing the last $4$ zero rows and
$4$ zero columns, we get
$$B=\begin{bmatrix}
1 &1   &0  &1  &0       \\
0 &0   &0  &0  &0       \\
0 &0   &1  &1  &1       \\
0 &0   &0  &0  &0       \\
0 &0   &0  &0  &0       \\
\end{bmatrix}.
$$
Finally, we obtain
$$
A'= \beta(A) =\begin{bmatrix}
0 &0  &1  &0 &0       \\
0 &0   &1  &0  &1       \\
0 &0   &1  &0  &0       \\
0 &0   &0  &0  &1       \\
0 &0   &0  &0  &1      \\
\end{bmatrix}
$$
  Conversely, given $A'\in \mathcal{B}(6)$, by
applying removal algorithm, we can get $A\in \mathcal{SM}(6)$, where
the removed rows and columns are illustrated in bold at each step of
the removal algorithm.
\end{example}


Combining the bijection between self-dual interval orders and
self-dual Fishburn matrices and Theorems \ref{th1} and \ref{th2}, we
get
  a bijective  proof of $(\ref{eq3})$.


  From  Theorems \ref{th1} and \ref{th2}, we have
$$ |\mathcal{M}(n,k,p)|=|\mathcal{ SM}(n,k,p)|=|\mathcal{B}(n,k,p)|.
$$
Given a matrix $M\in \mathcal{B}(n,k,0)$, we can get a matrix $A\in
\mathcal{RM}(n,k)$ by deleting the  first row and the first column.
Conversely, given a matrix $A'\in \mathcal{RM}(n,k)$, we can obtain
a matrix $M'\in \mathcal{B}(n,k,0)$ by inserting a zero   row and a
zero column before the first row and the first column. This yields
that
\begin{equation}\label{eq5}
  |\mathcal{M}(n,k,0)|=|\mathcal{B}(n,k,0)|=|\mathcal{RM}(n,k)|.
 \end{equation}
If $p>0$, then $\mathcal{B}(n,k,p)$ is the same as
$\mathcal{RM}(n,k,p)$. Hence, if $p>0$ then we have
\begin{equation}\label{eq6}
|\mathcal{ M}(n,k,p)|=|\mathcal{B}(n,k,p)|= |\mathcal{RM}(n,k,p)|.
\end{equation}
Therefore, we get combinatorial  proofs of (\ref{eq1}) and
(\ref{eq2}), in answer to the problem posed by Jel\'{i}nek
\cite{jel}.



Now we proceed to prove (\ref{eq8}).  Given a matrix $A\in
\mathcal{EM}(n,k)$ of dimension $2m$ for some integers $m\geq1$, let
$R(A)$ be its reduced matrix. We obtain a super triangular matrix
$A'$ from $A$ by inserting a zero column and a zero row immediately
after column $m$ and row $m$. By Lemma \ref{le}, we have $A'\in
\mathcal{SM}(n,k,0)$.

Conversely, given a matrix $A'\in \mathcal{SM}(n,k,0)$ of dimension
$2m+1$ for some integer $m\geq 1$, we can recover a self-dual matrix
$A\in \mathcal{EM}(n,k)$ as follows. First, we get a super
triangular matrix $B$ from $A'$ by deleting column $m+1$ and row
$m+1$. Let $A $ be a matrix with $B=R(A )$. Obviously, we have the
matrix $A\in \mathcal{EM}(n,k)$. Hence, we get that  $
|\mathcal{EM}(n,k)|=|\mathcal{SM}(n,k,0)|. $ By (\ref{eq5}), we
deduce that 
\begin{equation}\label{eq7}
|\mathcal{EM}(n,k)|=|\mathcal{SM}(n,k,0)|=|\mathcal{RM}(n,k)|.
\end{equation}
 From (\ref{eq5}) and ($\ref{eq6}$), we obtain that  
$$
\begin{array}{lll}
|\mathcal{M}(n,k)|&=&|\mathcal{M}(n,k,0)|+ \sum_{p\geq
1}|\mathcal{M}(n,k,p)|\\
&=&|\mathcal{RM}(n,k)|+\sum_{p\geq
1}|\mathcal{RM}(n,k,p)|\\
&=&2|\mathcal{RM}(n,k)|.
\end{array}
$$
Meanwhile, we have
$|\mathcal{M}(n,k)|=|\mathcal{EM}(n,k)|+|\mathcal{OM}(n,k)|$. Hence,
(\ref{eq8}) follows from (\ref{eq7}).



 \subsection*{Acknowledgements}
The authors  would like to thank the referee for helpful suggestions.

%--------------------------
\begin{thebibliography}{100}


\bibitem{Bog}
K.P.~Bogart.  \newblock An obvious proof of Fishburn's interval order theorem.
\newblock {\em Discrete Math.}, 118:239--242,  1993.

\bibitem{melon}
 M.~Bousquet-M\'elou, A.~Claesson, M.~Dukes, and S.~Kitaev.  \newblock  $(2+2)$-free posets, ascent sequences and pattern avoiding permutations. \newblock {\em
J. Combin. Theory Ser. A},    117:884--909,   2010.


\bibitem{cla1}
A.~Claesson, M.~Dukes, and M.~Kubitzke.  \newblock   Partition and composition
matrices.  \newblock {\em J.  Combin.  Theory Ser. A},   118:1624--1637,  2011.

\bibitem{Duck}
M.~Dukes, R.~Parviainen. \newblock Ascent sequences and upper triangular
matrices containing non-negative integers. \newblock {\em Electronic  J.
Combin.},    17:R53, 2010. 

\bibitem{Duck2}
M.~Dukes, S.~Kitaev, J.~Remmel, and E.~Steingr\'imsson. \newblock Enumerating
(2+2)-free posets by indistinguishable elements.  \newblock {\em Journal of  Combinatroics},  2:139--163, 2011.
\bibitem{Duck3}
M.~Dukes, V.~Jel\'inek, and M.~Kubitzke.   \newblock Composition matrices,
(2+2)-free posets and their specializations. \newblock {\em Electronic J.
Combin.},   18:P44,   2011.


\bibitem{fish1}
P. C.~Fishburn. \newblock   Interval lengths for interval orders: A
minimization problem.   \newblock {\em Discrete Math.},   47:63--82,  1983.
\bibitem{fish2}
P. C.~Fishburn.   \newblock Interval graphs and interval orders.  \newblock {\em Discrete
Math.},   55:135--149, 1985. 
\bibitem{fish3}
P. C.~Fishburn. \newblock {\em Interval orders and interval graphs: A study of
partially ordered sets}.   \newblock John Wiley \& Sons, 1985.

\bibitem{jel}
V.~Jel\'{i}nek.  \newblock Counting general and  self-dual interval orders. 
\newblock {\em J.  Combin.  Theory  Ser. A},   119:599--614,  2012. 

\bibitem{Kitaev}
S.~Kitaev,  J.~Remmel.   \newblock Enumerating $(2+2)$-free posets by the
number of minimal elements and other statistics.  \newblock {\em Discrete
Appl. Math.},   159:2098--2108,   2011.
\bibitem{Stoi}
A.~Stoimenow. \newblock Enumumeration of chord diagrams and an upper bound for
Vassiliev invariants. \newblock {\em J. Knot Theory Ramifications},     7:93--114, 1998.
\bibitem{zag}
D.~Zagier. \newblock Vassiliev invariants and a strange identity related to the
Dedekind eta-function.  \newblock {\em Topology},      40:945--960,    2001.
\end{thebibliography}
\end{document}
