col_{n-k} )$    \\
    \bottomrule
\end{tabular}
\end{center}
We further write $\prowp_p = \mathrm{col}(\prow_p)$ for the  column matched to  row $\prow_p$, and $\pcolp_p = \mathrm{row}(\pcol_p)$ for the  row matched to column $\pcol_p$.  Thus 
    \begin{align*}
        \mu
        & \;= \;
        \{ (\prow_1, \prowp_1), \ldots, (\prow_k, \prowp_k) \} \\
        &
        \; = \; 
        \{ (\pcolp_1, \pcol_1), \ldots, (\pcolp_k, \pcol_k) \} 
    \end{align*}
Note, however, that 
    \begin{align*}
        (\prow_p, \prowp_p) \neq (\pcolp_p, \pcol_p)
    \end{align*}
in general.


\subsection{The matching identity}
\label{sec:matchingidentity}

We may now formalize the statement that left-multiplication with $\DD$ ``matches columns to columns.''  Equation \eqref{eq_matchcolumn} contains both the statement and the proof.  Equation \eqref{eq_matchrow} encapsulates the dual statement that right-multiplication with $\DD$ ``matches rows to rows.''


\begin{lemma}[Matching identity for columns]
\label{lem:matchingidentity}
For any U-match decomposition $\RR \MM = \DD \CC$, one has 
    \begin{align}
        \DD \cdot \col_c(\CC) 
        & = 
        \col_c(\DD \cdot \CC) 
        \nonumber \\
        &=
        \col_c(\RR \cdot \MM)
        \nonumber\\
        &=
            \begin{cases}
                \col_{\mathrm{row}(c)} (\RR) \cdot \MM[\mathrm{row}(c), c] & c \text{ is a matched index } \\
                0 & else
            \end{cases}
        \label{eq_matchcolumn}
    \end{align}
\end{lemma}


\begin{lemma}[Matching identity for rows]
\label{lem:matchingidentityDUAL}
For any U-match decomposition $\RR \MM = \DD \CC$, one has 
    \begin{align}
        \row_r( \Ri) \cdot \DD 
        & = 
        \row_r( \Ri \cdot \DD )
        \nonumber \\
        &=
        \row_r(\MM \cdot \Ci)
        \nonumber\\
        &=
            \begin{cases}
                \row_{\mathrm{col}(r)} (\Ci) \cdot \MM[r, \mathrm{col}(r)] & r \text{ is a matched index } \\
                0 & else
            \end{cases}
        \label{eq_matchrow}
    \end{align}
\end{lemma}

\subsection{Linear dual spaces and matching}

The matching identity for rows (Lemma \ref{lem:matchingidentityDUAL}) has a natural interpretation in terms of linear dual spaces; this interpretation is not vital to our main narrative, but it does lend a complementary perspective.

Each length-$n$ row vector $v^*$ naturally determines a linear map $\mathbb K^n \to \mathbb K, \; u \mapsto v^* \cdot u$ from the space $\mathbb K^n$ of length-$n$ column vectors to the ground field $\mathbb K$.  Since $\Ci \CC = I$, the set $\{ \row_i(\Ci) : i \le n \}$ forms a basis dual to $\{ \col_j(\CC) : j \le n\}$, in the sense that $\row_i(\Ci) \cdot \col_j(\CC) = \delta_{ij}$, the Kronecker delta.

Viewed in this light, the matching identity for rows  states that the linear map of dual spaces $(\mathbb K^m)^* \to (\mathbb K^n)^*, \; v^* \mapsto (v^* \circ \DD)$ carries each element of the basis dual to $\RR$ either to 0 or to a nonzero scalar multiple of some element in the basis dual to $\CC$.


\subsection{Proper decomposition}

A  {U-match decomposition} $\RR \MM  = \DD \CC$ is \emph{proper} if both of the following axioms hold, where $\id^{n \times n}$ denotes the $n \times n$ identity matrix: 
    \begin{enumerate}[label=\textbf{(A\arabic*)}]
        \item \label{item:proper1} $\col_k(\MM) = 0 \implies \row_k(\CC)$ is the $k$th standard unit row vector.  This is equivalent to the condition that
            \begin{align*}
                \CC_{\upto{n} \npcols} = \id^{n\times n}_{\upto{n} \npcols}.
            \end{align*}
        \item \label{item:proper2} $\row_k(\MM) = 0 \implies \col_k(\RR)$ is the $k$th standard unit column vector; equivalently, 
            \begin{align*}
                \RR_{ \nprows \upto{m}} = \id^{m\times m}_{\nprows \upto{m}}.
            \end{align*}
    \end{enumerate}
    
Proper decompositions have useful properties we that will leverage in later sections.  Most of the algorithms that compute U-match decomposition actually compute \emph{proper} decompositions. 



    















\subsection{Existence}

Every matrix $\DD$ admits a proper U-match decomposition; \emph{a fortiori}, every matrix has a U-match decomposition.  We provide a constructive proof in \S\ref{sec:factorization_algorithms} (Algorithm \ref{alg_lrdec} and Proposition \ref{prop:correctnessofalgorithm1}).
These results are technical in nature, so we defer them to the end of the discussion.





\subsection{Uniqueness of matching arrays, non-uniquness of \COB{}s, and codetermination of proper \COB{}s}
\label{sec:uniqueCOMB}
 

A single matrix $\DD$ may admit multiple distinct U-match factorizations, and indeed multiple distinct proper U-match factorizations.  However, the associated matching array is unique.

\begin{example}[Proper \COB{}s are not uniqu]
Since $N \id = \id N$, any upper-unitriangular matrix can be a (co)domain \COB{} for mapping array $\DD = \id$.  
\end{example} 


\begin{theorem}[Matching arrays are unique]
\label{thm:matchingunique}
Let $\DD$ be a matrix. For any two U-match decompositions $\RR \MM = \DD \CC$ and $\stilde \RR \stilde \MM = \DD \stilde \CC$, one has $\MM = \stilde \MM$.
\end{theorem}
\begin{proof}
By vertically concatenating the associated diagrams from  Equation \eqref{eq:umatch} and reversing some arrows, one can obtain a U-match decomposition of form $\stilde{\RR}^{-1} \RR \MM = \stilde \MM \stilde{\CC}^{-1} \CC$. Multiplication by invertible upper triangular matrices does not change the rank of any submatrix in the lower-lefthand corner of an array, so the number of nonzero entries in each $p \times q$ submatrix in the lower lefthand corners of $\MM$ and $\stilde \MM$ is the same.  Thus, $\MM$ and $\stilde \MM$ have equal sparsity patterns.  Furthermore, every nonzero entry of a matching array remains the same after multiplication by a unitriangular matrix, so the nonzero elements of $\MM$ and $\stilde \MM$ are identical.
\end{proof}

In light of Theorem \ref{thm:matchingunique}, we may speak  of the  \underline{\smash{unique matching array}} associated to $\DD$ by U-match decomposition.\footnote{Theorem \ref{thm:matchingunique} reflects a deeper structural result concerning bifiltrations of linear spaces (or, more generally, modular lattices), c.f.\  Appendix \S\ref{sec:asideonordertheory}.}






However, in proper U-match decompositions $\DD$ determines three out of four blocks of both $\RR$ and $\CC$.  This can be shown using the ``inner identities'' which will be proved in Theorem  \ref{thm:umatchblockidentities}.


\begin{proposition}[Row and column operation matrices are ``mostly'' unique]
\label{prop:1blockdiff}