CMR  1.3.0
(Strongly) k-Modular and Unimodular Matrices

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: