Consider a matrix \( M \in \mathbb{Z}^{m \times n} \) of rank \( r \). The matrix \( M \) is called k-modular (for some \( k \in \{1,2,\dotsc \} \)) if these two conditions are satisfied:

for some column basis \( B \subseteq \{1,2,\dotsc,n\} \) of \( M \), the greatest common divisor of the determinants of all \(r \)-by- \( r \) submatrices of \( M_{\star,B} \) is equal to \( k \).
The matrix \( X \) such that \( M = M_{\star,B} X \) is totally unimodular.

In case \( M \) has full row-rank, the first property requires that the determinant of any basis matrix shall be \( k \), while the second property requires that \( M_{\star,B}^{-1} M \) is totally unimodular. Otherwise, \( M_{\star,B} \) is singular, and hence the property is more technical.

Note: k-modularity is independent of the choice of the column basis \( B \).

Additionally, \( M \) is called strongly k-modular if \( M \) and \( M^{\textsf{T}} \) are k-modular. The special cases with \( k = 1 \) is called unimodular and strongly unimodular, respectively.

Usage

The executable cmr-k-modular determines whether a given matrix \( M \) is \(k\)-modular (and determines \( k \)).

./cmr-k-modular [OPTION]... FILE

Options:

-i FORMAT Format of input FILE; default: dense.
-t Test \( M^{\textsf{T}} \) instead.
-s Test for strong \( k \)-modularity, i.e., test \( M \) and \( M^{\textsf{T}} \).
-u Test only for unimodularity, i.e., \( 1 \)-modularity.

Formats for matrices are dense-matrix and sparse-matrix. If FILE is -, then the input will be read from stdin.

C Interface

The functionality is defined in k_modular.h. The main functions are:

CMRtestKmodularity() tests a matrix for being \(k\)-modular.
CMRtestStrongKmodularity() tests a matrix for being strongly \(k\)-modular.
CMRtestUnimodularity() tests a matrix for being unimodular.
CMRtestStrongUnimodularity() tests a matrix for being strongly unimodular.