MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

One of the consequences of Seymour's characterization of regular matroids is the existence of a polynomial time recognition algorithm for totally unimodular matrices (i.e. matrices for which every square sub-determinant is in {0, 1, -1}).

But has anyone actually implemented it?

share|cite|improve this question
I guess I'll take the silence as a probable "no"... It seems like something that I would like to have done, but don't actually want to do.. – Gordon Royle Jun 8 '10 at 1:59
up vote 6 down vote accepted

EDIT. Walter and Trümper have announced on arXiv their implementation, with source code available, of two methods for testing total unimodularity. Their paper describes the technical details of the implementation / algorithm, and also provides several experimental results.

I found the following link for an implementation in R, where they claim to have a function for testing whether a matrix is totally unimodular. I have not checked which particular algorithm they use.

Link: R package

share|cite|improve this answer
The implementation mentioned already is available at this site. It is a C++ library with a straight-forward interface. – Xammy Jun 6 '12 at 7:14

To my knowledge no one has implemented the algorithm. A good reference though for someone thinking about it would be Truember's book "Matroid Decomposition" which contains a fairly simple description of the necessary steps.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.