x1
+x1
+x1
+x1
+x2
+x2
+x2
+x2
+x3
+x3
+x3
+x3
+x4
=x4
=x4
=x4
=Number format
Solution comments
Without description (answer only)
a
b
c
d
x
y
z
clear
i
Randomize
3131313131351515151515≈83137
How to solve a system by the Montante (Bareiss) method
Apply Bareiss-style integer-preserving elimination to the augmented matrix. Each pivot operation divides exactly by the previous pivot, so intermediate values stay integers throughout. Read the solution from the final reduced form.
Montante (Bareiss) worked example (5 equations)
Write the system of equations in matrix form:
5
1
0
1
0
1
5
1
0
1
0
1
4
1
0
1
0
1
5
1
0
1
0
1
4
7
8
6
8
6
To find the roots of a system of linear equations, using the
Montante (Bareiss algorithm)
method , we can transform the matrix form of the system so that the left part of the matrix becomes a identity, then on the right part we get the roots of the system;
2
Iteration 1A0
=
5
1
0
1
0
1
5
1
0
1
0
1
4
1
0
1
0
1
5
1
0
1
0
1
4
7
8
6
8
6
In the first iteration, the previous pivot element is always equal to 1:
p0
=
1
;
The current pivot element is equal to the element of the previous matrix (
A0
) with indices
1
,
1
:
p1
=
a0
0
1,1
=
5
;
Calculate the next matrix (
A1
) based on the previous matrix (
A0
);
1)
The line in which there is a pivot element is rewritten in the next matrix without changes;2)
Write zero in all elements of the column in which the pivot element is located, except for the pivot element itself;Write the initial matrix
A1
and mark the elements that we need to find as unknown:
A1
=
5
0
0
0
0
1
0
1
0
7
To find unknown elements use the following formula:
a1
0
i,j
=
a0
0
i,j
*
p1
-
a0
0
1,j
*
a0
0
i,1
p0
p0
is the previous pivot elementp1
is the current pivot elementa0
is the element of the previous matrix, calculated on the previous iterationa1
is the element of the next matrix, calculated on the current iterationi
is the row numberj
is the column numberⱯ(
i, j
)
∈ {2, 3, 4, 5} × {2, 3, 4, 5, 6}
A1
=
5
0
0
0
0
1
24
5
-1
5
0
5
20
5
0
1
-1
5
24
5
0
5
0
5
20
7
33
30
33
30
3
Iteration 2The current pivot element is equal to the element of the previous matrix (
A1
) with indices
2
,
2
:
p2
=
a1
0
2,2
=
24
;
Calculate the next matrix (
A2
) based on the previous matrix (
A1
);
1)
The line in which there is a pivot element is rewritten in the next matrix without changes;2)
Write zero in all elements of the column in which the pivot element is located, except for the pivot element itself;3)
Replace all previous pivot elements with p2;Write the initial matrix
A2
and mark the elements that we need to find as unknown:
A2
=
24
0
0
0
0
0
24
0
0
0
××××
5
××××
-1
××××
5
××××
33
To find unknown elements use the following formula:
a2
0
i,j
=
a1
0
i,j
*
p2
-
a1
0
2,j
*
a1
0
i,2
p1
p1
is the previous pivot elementp2
is the current pivot elementa1
is the element of the previous matrix, calculated on the previous iterationa2
is the element of the next matrix, calculated on the current iterationi
is the row numberj
is the column numberⱯ(
i, j
)
∈ {1, 3, 4, 5} × {3, 4, 5, 6}
A2
=
24
0
0
0
0
0
24
0
0
0
-1
5
91
25
-5
5
-1
25
115
25
-1
5
-5
25
91
27
33
111
165
111
4
Iteration 3The current pivot element is equal to the element of the previous matrix (
A2
) with indices
3
,
3
:
p3
=
a2
0
3,3
=
91
;
Calculate the next matrix (
A3
) based on the previous matrix (
A2
);
1)
The line in which there is a pivot element is rewritten in the next matrix without changes;2)
Write zero in all elements of the column in which the pivot element is located, except for the pivot element itself;3)
Replace all previous pivot elements with p3;Write the initial matrix
A3
and mark the elements that we need to find as unknown:
A3
=
91
0
0
0
0
0
91
0
0
0
0
0
91
0
0
××××
25
××××
-5
××××
111
To find unknown elements use the following formula:
a3
0
i,j
=
a2
0
i,j
*
p3
-
a2
0
3,j
*
a2
0
i,3
p2
p2
is the previous pivot elementp3
is the current pivot elementa2
is the element of the previous matrix, calculated on the previous iterationa3
is the element of the next matrix, calculated on the current iterationi
is the row numberj
is the column numberⱯ(
i, j
)
∈ {1, 2, 4, 5} × {4, 5, 6}
A3
=
91
0
0
0
0
0
91
0
0
0
0
0
91
0
0
20
-9
25
410
100
-4
20
-5
100
344
107
102
111
510
444
5
Iteration 4The current pivot element is equal to the element of the previous matrix (
A3
) with indices
4
,
4
:
p4
=
a3
0
4,4
=
410
;
Calculate the next matrix (
A4
) based on the previous matrix (
A3
);
1)
The line in which there is a pivot element is rewritten in the next matrix without changes;2)
Write zero in all elements of the column in which the pivot element is located, except for the pivot element itself;3)
Replace all previous pivot elements with p4;Write the initial matrix
A4
and mark the elements that we need to find as unknown:
A4
=
410
0
0
0
0
0
410
0
0
0
0
0
410
0
0
0
0
0
410
0
××××
100
××××
510
To find unknown elements use the following formula:
a4
0
i,j
=
a3
0
i,j
*
p4
-
a3
0
4,j
*
a3
0
i,4
p3
p3
is the previous pivot elementp4
is the current pivot elementa3
is the element of the previous matrix, calculated on the previous iterationa4
is the element of the next matrix, calculated on the current iterationi
is the row numberj
is the column numberⱯ(
i, j
)
∈ {1, 2, 3, 5} × {5, 6}
A4
=
410
0
0
0
0
0
410
0
0
0
0
0
410
0
0
0
0
0
410
0
-40
100
-50
100
1440
370
510
360
510
1440
6
Iteration 5The current pivot element is equal to the element of the previous matrix (
A4
) with indices
5
,
5
:
p5
=
a4
0
5,5
=
1440
;
Calculate the next matrix (
A5
) based on the previous matrix (
A4
);
1)
The line in which there is a pivot element is rewritten in the next matrix without changes;2)
Write zero in all elements of the column in which the pivot element is located, except for the pivot element itself;3)
Replace all previous pivot elements with p5;Write the initial matrix
A5
and mark the elements that we need to find as unknown:
A5
=
1440
0
0
0
0
0
1440
0
0
0
0
0
1440
0
0
0
0
0
1440
0
0
0
0
0
1440
××××
1440
To find unknown elements use the following formula:
a5
0
i,j
=
a4
0
i,j
*
p5
-
a4
0
5,j
*
a4
0
i,5
p4
p4
is the previous pivot elementp5
is the current pivot elementa4
is the element of the previous matrix, calculated on the previous iterationa5
is the element of the next matrix, calculated on the current iterationi
is the row numberj
is the column numberⱯ(
i, j
)
∈ {1, 2, 3, 4} × {6}
A5
=
1440
0
0
0
0
0
1440
0
0
0
0
0
1440
0
0
0
0
0
1440
0
0
0
0
0
1440
1440
1440
1440
1440
1440
7
System of linear equationsDivide each nonzero element of the matrix by
1440
;
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
Answer
Ax = bx
0
1
=
1
;
x
0
2
=
1
;
x
0
3
=
1
;
x
0
4
=
1
;
x
0
5
=
1
;
SIZE5×6METHODMontante (Bareiss algorithm)