The footprint form of a matrix: definition, properties, and an application (Q2158285)

Let \(A\) be a \(m\times n\) matrix over a field for which, to simplify the discussion below, we assume that there are no columns of zeros. Using elementary row operations we can reduce \(A\) to its well-known Row Reduced Echelon Form (RREF), \(A_{\mathrm{rref}}\). The authors propose a modified version of the RREF which they call the Row Reduced Footprint Form (RRFF), \( A_{\mathrm{rrff}}\). This keeps track not only of the leading nonzero entries but also of the trailing nonzero entries in nonzero rows. More precisely, if \(A\) has rank \(r\) then its reduced footprint form \(A_{\mathrm{rrff}}\) can be characterized by a list \([\lambda _{1},\tau _{1}],\dots,[\lambda _{r},\tau _{r}]\) of \(r\) pairs of indices with \(\lambda _{1}<\lambda _{2}< \dots<\lambda _{r}\) and \(\tau _{1},\dots,\tau _{r}\) distinct where: (i) For \(i=1,\dots,r\), the \(i\)-th row of \( A_{\mathrm{rrff}}\) has its leading nonzero entry equal to \(1\) and in column \(\lambda _{i}\) and its trailing nonzero entry in column \(\tau _{i}\); (ii) The entry in \((i,\tau _{i})\) is the only nonzero entry in its column; (iii) For \( i=r+1,\dots,m\), the rows of \(A_{\mathrm{rrff}}\) are equal to zero. It is proved that \(A\) can be reduced to one and only one matrix \(A^{\prime }\) satisfying these conditions using elementary row operations, and this is defined to be the RRFF \(A_{\mathrm{rrff}}\). The authors argue that the additional information provided by the RRFF can be useful in solving certain problems, specifically integer linear programming problems about multivalued decision diagrams (MDD), see [\textit{T. Kam} et al., Mult.-Valued Log. 4, No. 1--2, 9--62 (1998; Zbl 1025.94515)]. To support this claim they give numerical examples where RRFFs are used to obtain bounds to solutions of MDDs.