Montante's method

Montante's Method is a linear algebra method to calculate solutions to systems of linear equations, and finding matrix inverses, adjoints and determinants. It is named after its discoverer René Mario Montante.

Its main feature is working exclusively using integer arithmetic for integer matrices, which allows for exact results in computer implementations.

History

The method was developed in 1973 by René Mario Montante Pardo, from the Department of Mechanical and Electric Engineering of the Universidad Autónoma de Nuevo León, in Monterrey,México.

Method

The method is pivot-based, working through the matrix main diagonal and rewriting the matrix iteratively by using 2x2 determinants based on elements and pivot rows and columns. If the original matrix is integer, the method works using integers until the final step, yielding at worst rational results.

This is a pseudo-code implementation of a linear system solver for $Ax=B$ using Montante's method:

Input: An "n"x"n+1" matrix "M" holding $left(A|B\; ight)$. Output: An "n"x"n+1" matrix holding $left(dI\_n|x^prime\; ight)$ where $I\_n$ is the identity matrix of order $n$ $d$ is a scalar and $frac\{x^prime\}\{d\}$ is the solution p₀ ← 1 foreach t in 1 .. n p_t ← m_tt foreach i in 1 .. n except t foreach j in t+1 .. n m_ij ← ( p_t * m_ij - m_it * m_tj ) / p_t-1 m_kt ← 0 forall k ≠ t m_kk ← p forall k ≤ t return "M"

And an implementation in Ruby

def montante_solve( a ) nr = a.size nc = nr+1 # a must be n x n+1 m = Array.new # work on a copy (0 ... nr).each do |k| m [k] = Array.new(a [k] ) end p_pre = 1 # The previous pivot for t in ( 0 ... nr ) do p = m [t] [t] # The current pivot (0 .. t).each do |k| m [k] [k] = p end for i in 0 ... nr do for j in (t+1) ... nc do m [i] [j] = ( p * m [i] [j] - m [i] [t] * m [t] [j] ) / p_pre if i!=t end end p_pre = p (0 ... nr).each do |k| m [k] [t] = 0 end end return m end a = [ [2,-1,-3, 1, 3] , [1, 1,-2,-2, 2] , [3,-2, 1,-1,-2] , [1,-1, 1, 3, 1] ] p montante_solve( a )

Walkthrough

Given the following linear equation system with integer coefficients
:$2x\; -\; y\; -\; 3z\; +\; w\; =\; 3\; ,$:$x\; +\; y\; -\; 2z\; -\; 2w=\; 2\; ,$:$3x\; -\; 2y\; +\; z\; -\; w=\; -2\; qquad\; qquad\; (1)$:$x\; -\; y\; +\; z\; +\; 3w=\; 1\; ,$
The augmented matrix (including the results column) is:

:

First iteration: keep the first row (pivot row) as-is and zero-out all but the first elements in the pivot column;

:

The current pivot $p\_1\; =\; 2$ at $a\_\{11\}$ (the upper-leftmost cell), and the "previous" pivot $p\_0$ is 1.

Each of the elements in the rest of the matrix (except the pivot row and pivot column) are obtained by the formula

: $a^1\_\{ij\}\; leftarrow\; frac\{\; a\_\{ij\}\; p\_1\; -\; a\_\{1j\}\; a\_\{j1\}\; \}\{p\_0\}$

Thus

:

Second iteration: the new pivot is $p\_2\; =\; 3$ at $a^1\_\{22\}$

Keep the second (pivot) row as-is, zero-out the second column except the diagonal element, replace all previous pivot elements with $p\_2$. Then apply the determinant formula to the remaining elements, which form a submatrix holding columns 3 to 5 and lines 1, 3 and 4.

: $a^2\_\{ij\}\; leftarrow\; frac\{\; a^1\_\{ij\}\; p\_2\; -\; a^1\_\{2j\}\; a^1\_\{j2\}\; \}\{p\_1\}\; qquad\; forall\; (i,j)\; in\; left\{\; 1,3,4\; ight\}\; imes\; left\{\; 3,4,5\; ight\}$

:

Third iteration: as before, with pivot $p\_3\; =\; 16$ at $a^2\_\{33\}$.

:

Fourth iteration:

:

The solution to system (1) is then:

:$x\; =\; frac\; \{38\}\{50\}\; qquad\; y\; =\; frac\; \{70\}\{50\}\; qquad\; z\; =\; frac\; \{-35\}\{50\}\; qquadw\; =\; frac\; \{39\}\{50\}$