## Complexity of computing matrix rank over integers

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Does computing the rank of an integer matrix have complexity polynomial in the size of the input?

The Gaussian elimination algorithm is polynomial in the number of elementary operations (addition and multiplication), but the intermediate size of of the matrix entries may go up exponentially. Are there other algorithms with better complexity? Can anyone give a reference?

-

## 3 Answers

Gaussian elimination is a polynomial-time algorithm. While it may not be obvious on the first sight, it can be implemented so that the intermediate entries have only polynomial size (bit length), because they happen to be equal to determinants of certain submatrices of the original matrix (or ratios thereof, depending on the version). See e.g. Edmonds and Bareiss.

-

Right, using Bareiss' algorithm space needed is at most 0.5 n lg n + O(n) due to a theorem of Hadamard. This means that each operation takes time $O(n(\log n)^{2+\varepsilon})$ giving overall time complexity $O(n^4(\log n)^{2+\varepsilon}).$ – Charles Apr 28 2011 at 15:36

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

I asked more-or-less the same question 12 years ago on sci.math.num-analysis, but for the case when the integer entries are small. Thom Mulders replied describing this wonderful modular method.

-

The answer to your question is yes. Note that you can bound determinant(in fact you need to bound the size of lattice spanned by rows of the matrix) of the matrix with integer of size polynomial in the length input. Let $p$ be a prime with is large than this bound then the rank of the integer matrix will be equal to the rank of the matrix mod $p$.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 4, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8929191827774048, "perplexity_flag": "head"}