Montante's method

From Wikipedia, the free encyclopedia

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.

[edit] 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.

[edit] 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:

Algorithm MontanteLinearSolver
  Input: An nxn+1 matrix M holding \left(A|B\right).
  Output: An nxn+1 matrix holding \left(dI_n|x^\prime\right)
          where In is the identity matrix of order n
          d is a scalar and \frac{x^\prime}{d} is the solution
  
  p0 ← 1
  foreach t in 1 .. n
      pt ← mtt
      foreach i in 1 .. n except t
          foreach j in t+1 .. n
              mij ← ( pt * mij - mit * mtj ) / pt-1
      mkt ← 0 forall k ≠ t
      mkk ← p forall k ≤ t
  return M
  • "←" is a loose shorthand for "changes to". For instance, "largest ← item" means that the value of largest changes to the value of item.
  • "return" terminates the algorithm and outputs the value that follows.

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 )

[edit] 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:

A_0 = \begin{pmatrix} 2 & -1 & -3 & 1 & 3 \\ 1 & 1 & -2 & -2 & 2 \\ 3 & -2 & 1 & -1 &-2 \\ 1 & -1 & 1 & 3 & 1 \end{pmatrix}


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

A_1 = \begin{pmatrix} 2 & -1 & -3 & 1 & 3 \\ 0 & \cdots & \cdots & \cdots & \cdots \\ 0 & \cdots & \cdots & \cdots & \cdots\\ 0 & \cdots & \cdots & \cdots & \cdots \end{pmatrix}

The current pivot p1 = 2 at a11 (the upper-leftmost cell), and the "previous" pivot p0 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

A_1 = \begin{pmatrix} 2 & -1 & -3 & 1 & 3 \\ 0 & 3 & -1 & -5 & 1 \\ 0 & -1 & 11 & -5 &-13 \\ 0 & -1 & 5 & 5 & -1 \end{pmatrix}

Second iteration: the new pivot is p2 = 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 p2. 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 \right\} \times \left\{ 3,4,5 \right\}
A_2 = \begin{pmatrix} 3 & 0 & -5 & -1 & 5 \\ 0 & 3 & -1 & -5 & 1 \\ 0 & 0 & 16 & -10 &-19 \\ 0 & 0 & 7 & 5 & -1 \end{pmatrix}

Third iteration: as before, with pivot p3 = 16 at a^2_{33}.

A_3 = \begin{pmatrix} 16 & 0 & 0 & -22 & -5 \\ 0 & 16 & 0 & -30 & -1 \\ 0 & 0 & 16 & -10 & -19 \\ 0 & 0 & 0 & 50 & 39 \\ \end{pmatrix}

Fourth iteration:

A_4 = \begin{pmatrix} 50 & 0 & 0 & 0 & 38\\ 0 & 50 & 0 & 0 & 70\\ 0 & 0 & 50 & 0 & -35\\ 0 & 0 & 0 & 50 & 39 \\ \end{pmatrix}

The solution to system (1) is then:

x = \frac {38}{50} \qquad y = \frac {70}{50} \qquad z = \frac {-35}{50} \qquad w = \frac {39}{50}
Languages