471:
6548:
4666:
111:
4351:
6812:
984:
466:{\displaystyle {\begin{bmatrix}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{bmatrix}}\to {\begin{bmatrix}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{bmatrix}}}
1564:
1979:
108:. This final form is unique; in other words, it is independent of the sequence of row operations used. For example, in the following sequence of row operations (where two elementary operations on different rows are done at the first and third steps), the third and fourth matrices are the ones in row echelon form, and the final matrix is the unique reduced row echelon form.
1254:
5508:, caused by the possibility of dividing by very small numbers. If, for example, the leading coefficient of one of the rows is very close to zero, then to row-reduce the matrix, one would need to divide by that number. This means that any error which existed for the number that was close to zero would be amplified. Gaussian elimination is numerically stable for
2991:
713:
4661:{\displaystyle T={\begin{bmatrix}a&*&*&*&*&*&*&*&*\\0&0&b&*&*&*&*&*&*\\0&0&0&c&*&*&*&*&*\\0&0&0&0&0&0&d&*&*\\0&0&0&0&0&0&0&0&e\\0&0&0&0&0&0&0&0&0\end{bmatrix}},}
2679:
2310:
1378:
1807:
693:
701:
A matrix is said to be in reduced row echelon form if furthermore all of the leading coefficients are equal to 1 (which can be achieved by using the elementary row operation of type 2), and in every column containing a leading coefficient, all of the other entries in that column are zero (which can
579:
echelon form. So the lower left part of the matrix contains only zeros, and all of the zero rows are below the non-zero rows. The word "echelon" is used here because one can roughly think of the rows being ranked by their size, with the largest being at the top and the smallest being at the bottom.
1043:
578:
could be used to make one of those coefficients zero. Then by using the row swapping operation, one can always order the rows so that for every non-zero row, the leading coefficient is to the right of the leading coefficient of the row above. If this is the case, then matrix is said to be in row
3418:
is also eliminated from the third row, the result is a system of linear equations in triangular form, and so the first part of the algorithm is complete. From a computational point of view, it is faster to solve the variables in reverse order, a process known as back-substitution. One sees the
2876:
31:
2553:
2168:
500:, and can be divided into two parts. The first part (sometimes called forward elimination) reduces a given system to row echelon form, from which one can tell whether there are no solutions, a unique solution, or infinitely many solutions. The second part (sometimes called
979:{\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\qquad (L_{1})\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\qquad (L_{2})\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\qquad (L_{3})\end{alignedat}}}
3410:
487:
refers to the process until it has reached its upper triangular, or (unreduced) row echelon form. For computational reasons, when solving systems of linear equations, it is sometimes preferable to stop row operations before the matrix is completely reduced.
2432:
1686:
3500:
to refer only to the procedure until the matrix is in echelon form, and use the term Gauss–Jordan elimination to refer to the procedure which ends in reduced echelon form. The name is used because it is a variation of
Gaussian elimination as described by
3100:
992:. In practice, one does not usually deal with the systems in terms of equations, but instead makes use of the augmented matrix, which is more suitable for computer manipulations. The row reduction procedure may be summarized as follows: eliminate
585:
549:
If the matrix is associated to a system of linear equations, then these operations do not change the solution set. Therefore, if one's goal is to solve a system of linear equations, then using these row operations could make the problem easier.
4893:
Gaussian elimination and its variants can be used on computers for systems with thousands of equations and unknowns. However, the cost becomes prohibitive for systems with millions of equations. These large systems are generally solved using
3914:
1559:{\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&2y&{}+{}&z&{}={}&5&\end{alignedat}}}
3469:. Its use is illustrated in eighteen problems, with two to five equations. The first reference to the book by this title is dated to 179 AD, but parts of it were written as early as approximately 150 BC. It was commented on by
1974:{\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&&&-z&{}={}&1&\end{alignedat}}}
2769:
1249:{\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\end{alignedat}}}
2986:{\displaystyle {\begin{alignedat}{4}x&\quad &&\quad &&{}={}&2&\\&\quad &y&\quad &&{}={}&3&\\&\quad &&\quad &z&{}={}&-1&\end{alignedat}}}
3447:
row echelon form, as it is done in the table. The process of row reducing until the matrix is reduced is sometimes referred to as Gauss–Jordan elimination, to distinguish it from stopping after reaching echelon form.
697:
It is in echelon form because the zero row is at the bottom, and the leading coefficient of the second row (in the third column), is to the right of the leading coefficient of the first row (in the second column).
3619:
2674:{\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&\quad &&{}={}&7&\\&&y&\quad &&{}={}&3&\\&&&\quad &z&{}={}&-1&\end{alignedat}}}
2305:{\displaystyle {\begin{alignedat}{4}2x&{}+{}&y&&&{}={}7&\\&&{\tfrac {1}{2}}y&&&{}={}{\tfrac {3}{2}}&\\&&&{}-{}&z&{}={}1&\end{alignedat}}}
4845:
This complexity is a good measure of the time needed for the whole computation when the time for each arithmetic operation is approximately constant. This is the case when the coefficients are represented by
5333:
In particular, if one starts with integer entries, the divisions occurring in the algorithm are exact divisions resulting in integers. So, all intermediate entries and final entries are integers. Moreover,
3484:
in 1707 long after Newton had left academic life. The notes were widely imitated, which made (what is now called) Gaussian elimination a standard lesson in algebra textbooks by the end of the 18th century.
5325:
3288:
3493:
to solve the normal equations of least-squares problems. The algorithm that is taught in high school was named for Gauss only in the 1950s as a result of confusion over the history of the subject.
3480:. In 1670, he wrote that all the algebra books known to him lacked a lesson for solving simultaneous equations, which Newton then supplied. Cambridge University eventually published the notes as
3293:
3002:
2690:
2321:
1575:
4924:
in 1967. Independently, and almost simultaneously, Erwin
Bareiss discovered another algorithm, based on the following remark, which applies to a division-free variant of Gaussian elimination.
104:. Once all of the leading coefficients (the leftmost nonzero entry in each row) are 1, and every column containing a leading coefficient has zeros elsewhere, the matrix is said to be in
2316:
1570:
3818:
2039:
5384:
5436:
2997:
5546:. The choice of an ordering on the variables is already implicit in Gaussian elimination, manifesting as the choice to work from left to right when selecting pivot positions.
5063:
3521:
To explain how
Gaussian elimination allows the computation of the determinant of a square matrix, we have to recall how the elementary row operations change the determinant:
3505:
in 1888. However, the method also appears in an article by Clasen published in the same year. Jordan and Clasen probably discovered Gauss–Jordan elimination independently.
3513:
Historically, the first application of the row reduction method is for solving systems of linear equations. Below are some other important applications of the algorithm.
5129:
5096:
4282:
4076:
3678:
5186:
5216:
5156:
5006:
4979:
4952:
3199:
2868:
2545:
2155:
1799:
1370:
523:, while the second part writes the original matrix as the product of a uniquely determined invertible matrix and a uniquely determined reduced row echelon matrix.
82:
to modify the matrix until the lower left-hand corner of the matrix is filled with zeros, as much as possible. There are three types of elementary row operations:
6257:
2881:
2558:
2173:
1812:
1383:
1048:
718:
688:{\displaystyle {\begin{bmatrix}0&\color {red}{\mathbf {2} }&1&-1\\0&0&\color {red}{\mathbf {3} }&1\\0&0&0&0\end{bmatrix}}.}
2685:
5697:
may be required if, at the pivot place, the entry of the matrix is zero. In any case, choosing the largest possible absolute value of the pivot improves the
3562:
3950:
3465:
6306:
6406:
4112:
6797:
4775:
unknowns by performing row operations on the matrix until it is in echelon form, and then solving for each unknown in reverse order, requires
6352:
6330:
6288:
6265:
6181:
6146:
6127:
6104:
5976:
5786:
4870:
is a variant of
Gaussian elimination that avoids this exponential growth of the intermediate entries; with the same arithmetic complexity of
3918:
To find the inverse of this matrix, one takes the following matrix augmented by the identity and row-reduces it as a 3 × 6 matrix:
5704:
Upon completion of this procedure the matrix will be in row echelon form and the corresponding system may be solved by back substitution.
6081:
4763:
required to perform row reduction is one way of measuring the algorithm's computational efficiency. For example, to solve a system of
3698:(number of operations in a linear combination times the number of sub-determinants to compute, which are determined by their columns)
6836:
5927:
3720:
A variant of
Gaussian elimination called Gauss–Jordan elimination can be used for finding the inverse of a matrix, if it exists. If
5330:
Bareiss' main remark is that each matrix entry generated by this variant is the determinant of a submatrix of the original matrix.
5221:
6787:
3644:
504:) continues to use row operations until the solution is found; in other words, it puts the matrix into reduced row echelon form.
511:
of the original matrix. The elementary row operations may be viewed as the multiplication on the left of the original matrix by
6749:
6685:
5539:
6340:
3547:
be the product of the scalars by which the determinant has been multiplied, using the above rules. Then the determinant of
5852:
4348:. In this way, for example, some 6 × 9 matrices can be transformed to a matrix that has a row echelon form like
3115:
2784:
2447:
2054:
1701:
1271:
6841:
6527:
6399:
6632:
6482:
4326:, which we know is the inverse desired. This procedure for finding the inverse works for square matrices of any size.
515:. Alternatively, a sequence of elementary operations that reduces a single row may be viewed as multiplication by a
507:
Another point of view, which turns out to be very useful to analyze the algorithm, is that row reduction produces a
6537:
6431:
5338:
provides an upper bound on the absolute values of the intermediate and final entries, and thus a bit complexity of
4899:
3502:
3405:{\displaystyle {\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2},\\L_{3}+L_{1}&\to L_{3}.\end{aligned}}}
564:
For each row in a matrix, if the row does not consist of only zeros, then the leftmost nonzero entry is called the
51:
988:
The table below is the row reduction process applied simultaneously to the system of equations and its associated
6777:
6426:
5535:
5443:
4847:
2427:{\displaystyle {\begin{aligned}L_{1}-L_{3}&\to L_{1}\\L_{2}+{\tfrac {1}{2}}L_{3}&\to L_{2}\end{aligned}}}
1681:{\displaystyle {\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2}\\L_{3}+L_{1}&\to L_{3}\end{aligned}}}
497:
79:
6652:
5718:
6769:
5513:
5453:
As a corollary, the following problems can be solved in strongly polynomial time with the same bit complexity:
4917:
4887:
105:
4083:
3921:
6815:
6522:
6392:
5713:
1985:
6093:
Queueing
Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications
5327:
This produces a row echelon form that has the same zero entries as with the standard
Gaussian elimination.
3095:{\displaystyle {\begin{aligned}L_{1}-L_{2}&\to L_{1}\\{\tfrac {1}{2}}L_{1}&\to L_{1}\end{aligned}}}
710:
Suppose the goal is to find and describe the set of solutions to the following system of linear equations:
6579:
6512:
6502:
6299:
5341:
4080:
By performing row operations, one can check that the reduced row echelon form of this augmented matrix is
3489:
in 1810 devised a notation for symmetric elimination that was adopted in the 19th century by professional
5950:
5396:
582:
For example, the following matrix is in row echelon form, and its leading coefficients are shown in red:
6739:
6594:
6589:
6584:
6517:
6462:
5492:
59:
34:
Animation of
Gaussian elimination. Red row eliminates the following rows, green rows change their order.
5011:
3208:
The second column describes which row operations have just been performed. So for the first step, the
6569:
6556:
6447:
6073:
5739:
5564:
5462:
3486:
3456:
The method of
Gaussian elimination appears – albeit without proof – in the Chinese mathematical text
539:
508:
75:
55:
5516:
matrices. For general matrices, Gaussian elimination is usually considered to be stable, when using
4751:
All of this applies also to the reduced row echelon form, which is a particular row echelon format.
6782:
6662:
6637:
6487:
6169:
5954:
5946:
5698:
5529:
5509:
5505:
5335:
4834:, where each arithmetic operation take a unit of time, independently of the size of the inputs) of
566:
531:
There are three types of elementary row operations which may be performed on the rows of a matrix:
5620:, meaning that the original matrix is lost for being eventually replaced by its row-echelon form.
3443:
Instead of stopping once the matrix is in echelon form, one could continue until the matrix is in
6492:
6218:
6200:
6096:
6016:
5877:
5689:
This algorithm differs slightly from the one discussed earlier, by choosing a pivot with largest
5439:
6379:
3909:{\displaystyle A={\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}}.}
30:
3700:. Even on the fastest computers, these two methods are impractical or almost impracticable for
6690:
6647:
6574:
6467:
6348:
6326:
6284:
6261:
6177:
6142:
6123:
6100:
6077:
5972:
5958:
5923:
5907:
5869:
5782:
4911:
4867:
4287:
3772:. Now through application of elementary row operations, find the reduced echelon form of this
3737:
3715:
3685:
574:) of that row. So if two leading coefficients are in the same column, then a row operation of
512:
501:
97:
71:
5101:
5068:
3650:
6695:
6599:
6452:
6210:
6045:
5964:
5915:
5861:
5590:
5161:
4895:
4699:
989:
559:
520:
516:
101:
5986:
5194:
5134:
4984:
4957:
4930:
3106:
2775:
2438:
2045:
1692:
1262:
475:
Using row operations to convert a matrix into reduced row echelon form is sometimes called
6754:
6547:
6507:
6497:
6249:
5982:
5850:
Althoen, Steven C.; McLaughlin, Renate (1987), "Gauss–Jordan reduction: a brief history",
5387:
4859:
4831:
3750:
1019:
2764:{\displaystyle {\begin{aligned}2L_{2}&\to L_{2}\\-L_{3}&\to L_{3}\end{aligned}}}
6759:
6744:
6680:
6415:
6280:
6230:
5690:
5543:
5485:
5447:
4863:
3682:(number of summands in the formula times the number of multiplications in each summand)
3490:
5776:
4898:. Specific methods exist for systems whose coefficients follow a regular pattern (see
6830:
6792:
6715:
6675:
6642:
6622:
6165:
6119:
5963:, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin,
5912:
Proceedings of the 1997 international symposium on
Symbolic and algebraic computation
5517:
67:
6222:
5559:, there cannot be a polynomial time analog of Gaussian elimination for higher-order
6725:
6614:
6564:
6457:
6012:
4921:
4862:
exactly represented, the intermediate entries can grow exponentially large, so the
4851:
4711:
3769:
3528:
Multiplying a row by a nonzero scalar multiplies the determinant by the same scalar
3477:
3457:
6358:
6191:
Grcar, Joseph F. (2011a), "How ordinary elimination became Gaussian elimination",
3788:
is invertible if and only if the left block can be reduced to the identity matrix
54:. It consists of a sequence of row-wise operations performed on the corresponding
6705:
6670:
6627:
6472:
6322:
5468:
5393:
Moreover, as an upper bound on the size of final entries is known, a complexity
63:
3531:
Adding to one row a scalar multiple of another does not change the determinant.
6734:
6477:
6049:
5968:
5597:
5520:, even though there are examples of stable matrices for which it is unstable.
4760:
3696:
operations if the sub-determinants are memorized for being computed only once
3635:
17:
6214:
6091:
Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor S. (2006),
5873:
5740:"DOCUMENTA MATHEMATICA, Vol. Extra Volume: Optimization Stories (2012), 9-14"
6532:
6037:
47:
5919:
78:(1777–1855). To perform row reduction on a matrix, one uses a sequence of
6700:
6300:"Numerical Methods with Applications: Chapter 04.06 Gaussian Elimination"
4718:
has a basis consisting of its columns 1, 3, 4, 7 and 9 (the columns with
5701:
of the algorithm, when floating point is used for representing numbers.
5881:
5616:
with the indices starting from 1. The transformation is performed
5560:
5550:
4855:
4296:
the product of these elementary matrices, we showed, on the left, that
3470:
5914:. ISSAC '97. Kihei, Maui, Hawaii, United States: ACM. pp. 28–31.
6710:
5644:
3440:. So there is a unique solution to the original system of equations.
6158:
Undergraduate Convexity: From Fourier and Motzkin to Kuhn and Tucker
5865:
3614:{\displaystyle \det(A)={\frac {\prod \operatorname {diag} (B)}{d}}.}
5775:
Timothy Gowers; June Barrow-Green; Imre Leader (8 September 2008).
5555:
96:
Using these operations, a matrix can always be transformed into an
6205:
6021:
29:
6384:
5721:- another process for bringing a matrix into some canonical form.
1022:. Then, using back-substitution, each unknown can be solved for.
5682:
j = k + 1 ... n: A := A - A * f /*
2161:
The matrix is now in echelon form (also called triangular form)
6388:
6339:
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007),
5908:"On the worst-case complexity of integer Gaussian elimination"
5320:{\textstyle {\frac {r_{k,k}R_{i}-r_{i,k}R_{k}}{r_{k-1,k-1}}}.}
4927:
In standard Gaussian elimination, one subtracts from each row
4286:
One can think of each row operation as the left product by an
3736:
square matrix, then one can use row reduction to compute its
58:
of coefficients. This method can also be used to compute the
5670:
i = h + 1 ... m: f := A / A /*
5575:
As explained above, Gaussian elimination transforms a given
4748:
can be written as linear combinations of the basis columns.
702:
be achieved by using elementary row operations of type 3).
5549:
Computing the rank of a tensor of order greater than 2 is
6319:
Schaum's outline of theory and problems of linear algebra
5542:. This generalization depends heavily on the notion of a
4334:
The Gaussian elimination algorithm can be applied to any
3800:. If the algorithm is unable to reduce the left block to
6141:, STATISTICS: Textbooks and Monographs, Marcel Dekker,
6347:(3rd ed.), New York: Cambridge University Press,
5224:
4366:
3833:
3794:; in this case the right block of the final matrix is
3310:
3050:
2382:
2250:
2222:
1905:
1877:
1592:
1476:
1448:
594:
384:
294:
204:
120:
5399:
5344:
5197:
5164:
5137:
5104:
5071:
5014:
4987:
4960:
4933:
4354:
4086:
3924:
3821:
3653:
3565:
3291:
3109:
3000:
2879:
2778:
2688:
2556:
2441:
2319:
2171:
2048:
1988:
1810:
1695:
1573:
1381:
1265:
1046:
716:
588:
114:
4920:
algorithm for Gaussian elimination was published by
3285:. These row operations are labelled in the table as
6768:
6724:
6661:
6613:
6555:
6440:
5960:
Geometric algorithms and combinatorial optimization
5860:(2), Mathematical Association of America: 130–142,
5686:*/ h := h + 1 k := k + 1
5474:Computing a solution of a rational equation system
3535:If Gaussian elimination applied to a square matrix
519:. Then the first part of the algorithm computes an
6345:Numerical Recipes: The Art of Scientific Computing
6015:(2009-11-07). "Most tensor problems are NP-hard".
5430:
5378:
5319:
5210:
5180:
5150:
5123:
5090:
5057:
5000:
4973:
4946:
4660:
4276:
4070:
3908:
3672:
3613:
3555:of the product of the elements of the diagonal of
3525:Swapping two rows multiplies the determinant by −1
3404:
3193:
3094:
2985:
2862:
2763:
2673:
2539:
2426:
2304:
2149:
2033:
1973:
1793:
1680:
1558:
1364:
1248:
978:
687:
465:
27:Algorithm for solving systems of linear equations
5191:Bareiss variant consists, instead, of replacing
3566:
5672:Fill with zeros the lower part of pivot column:
5538:is a generalization of Gaussian elimination to
5528:Gaussian elimination can be performed over any
4744:), and the stars show how the other columns of
545:Adding a scalar multiple of one row to another.
6254:Accuracy and Stability of Numerical Algorithms
6400:
6305:(1st ed.). University of South Florida.
5998:
5676:Do for all remaining elements in current row:
3476:The method in Europe stems from the notes of
8:
6238:Notices of the American Mathematical Society
5653:No pivot in this column, pass to next column
3815:For example, consider the following matrix:
92:Adding a multiple of one row to another row.
6036:Kurgalin, Sergei; Borzunov, Sergei (2021).
5893:
5781:. Princeton University Press. p. 607.
4818:subtractions, for a total of approximately
4668:where the stars are arbitrary entries, and
6407:
6393:
6385:
5674:*/ A := 0 /*
496:The process of row reduction makes use of
6317:Lipson, Marc; Lipschutz, Seymour (2001),
6204:
6020:
5419:
5401:
5400:
5398:
5364:
5346:
5345:
5343:
5288:
5277:
5261:
5248:
5232:
5225:
5223:
5202:
5196:
5169:
5163:
5142:
5136:
5109:
5103:
5076:
5070:
5040:
5031:
5019:
5013:
4992:
4986:
4965:
4959:
4938:
4932:
4690:are nonzero entries. This echelon matrix
4361:
4353:
4253:
4241:
4229:
4200:
4183:
4154:
4142:
4130:
4111:
4093:
4085:
3949:
3931:
3923:
3828:
3820:
3660:
3652:
3581:
3564:
3466:The Nine Chapters on the Mathematical Art
3389:
3372:
3359:
3342:
3325:
3309:
3300:
3292:
3290:
3114:
3108:
3082:
3065:
3049:
3039:
3022:
3009:
3001:
2999:
2968:
2963:
2936:
2931:
2904:
2899:
2880:
2878:
2783:
2777:
2751:
2734:
2717:
2700:
2689:
2687:
2656:
2651:
2626:
2621:
2596:
2591:
2576:
2571:
2557:
2555:
2494:
2477:
2446:
2440:
2414:
2397:
2381:
2372:
2358:
2341:
2328:
2320:
2318:
2292:
2287:
2276:
2271:
2249:
2247:
2242:
2221:
2209:
2204:
2191:
2186:
2172:
2170:
2099:
2087:
2053:
2047:
2025:
2012:
1993:
1987:
1959:
1954:
1928:
1923:
1904:
1900:
1895:
1876:
1862:
1857:
1846:
1841:
1830:
1825:
1811:
1809:
1746:
1734:
1700:
1694:
1668:
1651:
1638:
1624:
1607:
1591:
1582:
1574:
1572:
1544:
1539:
1528:
1523:
1499:
1494:
1475:
1471:
1466:
1447:
1433:
1428:
1417:
1412:
1401:
1396:
1382:
1380:
1270:
1264:
1231:
1226:
1212:
1207:
1196:
1191:
1163:
1158:
1144:
1139:
1128:
1123:
1098:
1093:
1082:
1077:
1066:
1061:
1047:
1045:
963:
941:
936:
922:
917:
906:
901:
875:
853:
848:
834:
829:
818:
813:
787:
768:
763:
752:
747:
736:
731:
717:
715:
640:
639:
604:
603:
589:
587:
379:
289:
199:
115:
113:
6231:"Mathematicians of Gaussian elimination"
5762:
4706:is 5, since there are 5 nonzero rows in
2160:
1026:
6277:A History of Mathematics, Brief Version
5731:
5131:are the entries in the pivot column of
4694:contains a wealth of information about
6798:Comparison of linear algebra libraries
5837:
5813:
5801:
5778:The Princeton Companion to Mathematics
2034:{\displaystyle L_{3}+-4L_{2}\to L_{3}}
89:Multiplying a row by a nonzero number,
6070:An Introduction to Numerical Analysis
5941:
5939:
5906:Fang, Xin Gui; Havas, George (1997).
5825:
5567:representations of order-2 tensors).
7:
5379:{\displaystyle {\tilde {O}}(n^{5}),}
4316:. On the right, we kept a record of
492:Definitions and example of algorithm
6116:A Contextual History of Mathematics
5431:{\displaystyle {\tilde {O}}(n^{4})}
3643:arithmetic operations, while using
575:
6038:"Algebra and Geometry with Python"
5629:Initialization of the pivot column
25:
6139:Linear Least Squares Computations
5853:The American Mathematical Monthly
638:
602:
6811:
6810:
6788:Basic Linear Algebra Subprograms
6546:
6312:from the original on 2012-09-07.
5604:denotes the entry of the matrix
5488:of a nonsingular rational matrix
5058:{\displaystyle r_{i,k}/r_{k,k},}
3645:Leibniz formula for determinants
1018:. This will put the system into
641:
605:
538:Multiplying a row by a non-zero
6686:Seven-dimensional cross product
6298:Kaw, Autar; Kalu, Egwu (2010).
6176:(3rd ed.), Johns Hopkins,
5655:*/ k := k + 1
5625:Initialization of the pivot row
5540:systems of polynomial equations
3710:Finding the inverse of a matrix
3633:matrix, this method needs only
2953:
2949:
2925:
2917:
2893:
2889:
2641:
2615:
2585:
955:
867:
779:
5425:
5412:
5406:
5370:
5357:
5351:
4101:
4094:
4087:
3939:
3932:
3925:
3667:
3654:
3599:
3593:
3575:
3569:
3539:produces a row echelon matrix
3382:
3335:
3075:
3032:
2744:
2710:
2407:
2351:
2018:
1661:
1617:
969:
956:
881:
868:
793:
780:
376:
286:
196:
1:
6068:Atkinson, Kendall A. (1989),
5684:Increase pivot row and column
5532:, not just the real numbers.
4878:, it has a bit complexity of
3753:is augmented to the right of
100:, and in fact one that is in
6528:Eigenvalues and eigenvectors
5664:Do for all rows below pivot:
2872:
2549:
2164:
1803:
1374:
1039:
74:. The method is named after
5461:given rational vectors are
3740:, if it exists. First, the
52:systems of linear equations
6858:
6229:Grcar, Joseph F. (2011b),
6137:Farebrother, R.W. (1988),
6072:(2nd ed.), New York:
5647:(i = h ... m, abs(A))
4909:
4900:system of linear equations
4854:. If the coefficients are
4826:operations. Thus it has a
4714:spanned by the columns of
3713:
3496:Some authors use the term
557:
6806:
6544:
6422:
6380:Interactive didactic tool
6114:Calinger, Ronald (1999),
6050:10.1007/978-3-030-61541-3
5999:Golub & Van Loan 1996
5969:10.1007/978-3-642-78240-4
4866:is exponential. However,
4850:or when they belong to a
4330:Computing ranks and bases
1009:from all equations below
996:from all equations below
498:elementary row operations
483:. In this case, the term
80:elementary row operations
6837:Numerical linear algebra
6275:Katz, Victor J. (2004),
6215:10.1016/j.hm.2010.06.003
5504:One possible problem is
4918:strongly-polynomial time
4888:strongly-polynomial time
4755:Computational efficiency
3623:Computationally, for an
706:Example of the algorithm
479:Gauss–Jordan elimination
106:reduced row echelon form
70:, and the inverse of an
5714:Fangcheng (mathematics)
5124:{\displaystyle r_{k,k}}
5091:{\displaystyle r_{i,k}}
4277:{\displaystyle =\left.}
4071:{\displaystyle =\left.}
3673:{\displaystyle (n\,n!)}
3482:Arithmetica Universalis
535:Interchanging two rows.
98:upper triangular matrix
6513:Row and column vectors
5662:(h, i_max) /*
5536:Buchberger's algorithm
5432:
5380:
5321:
5212:
5182:
5181:{\displaystyle R_{k},}
5152:
5125:
5092:
5059:
5002:
4975:
4948:
4886:, and has therefore a
4848:floating-point numbers
4662:
4278:
4072:
3910:
3674:
3615:
3517:Computing determinants
3406:
3195:
3096:
2987:
2864:
2765:
2675:
2541:
2428:
2306:
2151:
2035:
1975:
1795:
1682:
1560:
1366:
1250:
980:
689:
467:
35:
6518:Row and column spaces
6463:Scalar multiplication
6074:John Wiley & Sons
6011:Hillar, Christopher;
5920:10.1145/258726.258740
5643:*/ i_max :=
5506:numerical instability
5438:can be obtained with
5433:
5381:
5322:
5213:
5211:{\displaystyle R_{i}}
5183:
5153:
5151:{\displaystyle R_{i}}
5126:
5093:
5060:
5003:
5001:{\displaystyle R_{k}}
4976:
4974:{\displaystyle R_{k}}
4949:
4947:{\displaystyle R_{i}}
4828:arithmetic complexity
4802:multiplications, and
4761:arithmetic operations
4663:
4279:
4073:
3911:
3675:
3616:
3407:
3196:
3194:{\displaystyle \left}
3097:
2988:
2865:
2863:{\displaystyle \left}
2766:
2676:
2542:
2540:{\displaystyle \left}
2429:
2307:
2152:
2150:{\displaystyle \left}
2036:
1976:
1796:
1794:{\displaystyle \left}
1683:
1561:
1367:
1365:{\displaystyle \left}
1251:
1005:, and then eliminate
981:
690:
468:
33:
6653:Gram–Schmidt process
6605:Gaussian elimination
6193:Historia Mathematica
6170:Van Loan, Charles F.
5955:Schrijver, Alexander
5719:Gram–Schmidt process
5641:Find the k-th pivot:
5495:of a rational matrix
5471:of a rational matrix
5463:linearly independent
5444:Chinese remaindering
5397:
5342:
5222:
5195:
5162:
5135:
5102:
5069:
5012:
4985:
4958:
4954:below the pivot row
4931:
4352:
4084:
3922:
3819:
3651:
3563:
3498:Gaussian elimination
3487:Carl Friedrich Gauss
3473:in the 3rd century.
3289:
3107:
2998:
2877:
2776:
2686:
2554:
2439:
2317:
2169:
2046:
1986:
1808:
1693:
1571:
1379:
1263:
1044:
714:
586:
509:matrix decomposition
485:Gaussian elimination
112:
76:Carl Friedrich Gauss
40:Gaussian elimination
6842:Exchange algorithms
6783:Numerical stability
6663:Multilinear algebra
6638:Inner product space
6488:Linear independence
6174:Matrix Computations
5699:numerical stability
5510:diagonally dominant
5500:Numeric instability
5442:followed either by
5440:modular computation
5336:Hadamard inequality
3812:is not invertible.
3782:matrix. The matrix
3551:is the quotient by
3258:is eliminated from
3212:is eliminated from
1030:System of equations
567:leading coefficient
513:elementary matrices
6493:Linear combination
6325:, pp. 69–80,
6156:Lauritzen, Niels,
6097:Wiley-Interscience
5816:, pp. 783–785
5804:, pp. 169–172
5765:, pp. 234–236
5627:*/ k := 1 /*
5428:
5376:
5317:
5208:
5178:
5148:
5121:
5088:
5055:
4998:
4971:
4944:
4868:Bareiss' algorithm
4658:
4649:
4274:
4265:
4068:
4059:
3906:
3897:
3670:
3611:
3460:Rectangular Arrays
3402:
3400:
3319:
3191:
3185:
3092:
3090:
3059:
2983:
2981:
2860:
2854:
2761:
2759:
2671:
2669:
2537:
2531:
2424:
2422:
2391:
2302:
2300:
2259:
2231:
2147:
2141:
2031:
1971:
1969:
1914:
1886:
1791:
1785:
1678:
1676:
1601:
1556:
1554:
1485:
1457:
1362:
1356:
1246:
1244:
976:
974:
685:
676:
646:
610:
463:
457:
370:
280:
190:
86:Swapping two rows,
36:
6824:
6823:
6691:Geometric algebra
6648:Kronecker product
6483:Linear projection
6468:Vector projection
6354:978-0-521-88068-8
6332:978-0-07-136200-9
6290:978-0-321-16193-2
6267:978-0-89871-521-7
6183:978-0-8018-5414-9
6148:978-0-8247-7661-9
6129:978-0-02-318285-3
6106:978-0-471-79156-0
5978:978-3-642-78242-8
5947:Grötschel, Martin
5788:978-0-691-11880-2
5651:A = 0 /*
5596:In the following
5589:into a matrix in
5514:positive-definite
5409:
5354:
5312:
4912:Bareiss algorithm
4906:Bareiss algorithm
4896:iterative methods
4306:, and therefore,
4288:elementary matrix
4261:
4249:
4237:
4208:
4191:
4162:
4150:
4138:
3716:Invertible matrix
3699:
3686:Laplace expansion
3683:
3606:
3318:
3204:
3203:
3058:
2502:
2485:
2390:
2258:
2230:
2107:
2095:
1913:
1885:
1754:
1742:
1600:
1484:
1456:
1036:Augmented matrix
502:back substitution
72:invertible matrix
62:of a matrix, the
16:(Redirected from
6849:
6814:
6813:
6696:Exterior algebra
6633:Hadamard product
6550:
6538:Linear equations
6409:
6402:
6395:
6386:
6368:
6367:
6366:
6357:, archived from
6335:
6313:
6311:
6304:
6293:
6270:
6256:(2nd ed.),
6250:Higham, Nicholas
6245:
6235:
6225:
6208:
6186:
6160:
6151:
6132:
6109:
6095:(2nd ed.),
6086:
6054:
6053:
6033:
6027:
6026:
6024:
6008:
6002:
5996:
5990:
5989:
5943:
5934:
5933:
5903:
5897:
5894:Farebrother 1988
5891:
5885:
5884:
5847:
5841:
5835:
5829:
5823:
5817:
5811:
5805:
5799:
5793:
5792:
5772:
5766:
5760:
5754:
5753:
5751:
5750:
5736:
5695:partial pivoting
5615:
5611:
5607:
5603:
5591:row-echelon form
5588:
5584:
5558:
5553:. Therefore, if
5518:partial pivoting
5457:Testing whether
5437:
5435:
5434:
5429:
5424:
5423:
5411:
5410:
5402:
5385:
5383:
5382:
5377:
5369:
5368:
5356:
5355:
5347:
5326:
5324:
5323:
5318:
5313:
5311:
5310:
5283:
5282:
5281:
5272:
5271:
5253:
5252:
5243:
5242:
5226:
5217:
5215:
5214:
5209:
5207:
5206:
5187:
5185:
5184:
5179:
5174:
5173:
5157:
5155:
5154:
5149:
5147:
5146:
5130:
5128:
5127:
5122:
5120:
5119:
5097:
5095:
5094:
5089:
5087:
5086:
5064:
5062:
5061:
5056:
5051:
5050:
5035:
5030:
5029:
5007:
5005:
5004:
4999:
4997:
4996:
4980:
4978:
4977:
4972:
4970:
4969:
4953:
4951:
4950:
4945:
4943:
4942:
4885:
4877:
4860:rational numbers
4841:
4825:
4817:
4801:
4785:
4774:
4768:
4747:
4743:
4739:
4717:
4709:
4705:
4697:
4693:
4689:
4667:
4665:
4664:
4659:
4654:
4653:
4347:
4343:
4325:
4315:
4305:
4295:
4283:
4281:
4280:
4275:
4270:
4266:
4262:
4254:
4250:
4242:
4238:
4230:
4209:
4201:
4192:
4184:
4163:
4155:
4151:
4143:
4139:
4131:
4097:
4077:
4075:
4074:
4069:
4064:
4060:
3935:
3915:
3913:
3912:
3907:
3902:
3901:
3811:
3805:
3799:
3793:
3787:
3781:
3768:
3758:
3749:
3735:
3725:
3705:
3697:
3695:
3684:, and recursive
3681:
3679:
3677:
3676:
3671:
3642:
3632:
3620:
3618:
3617:
3612:
3607:
3602:
3582:
3558:
3554:
3550:
3546:
3542:
3538:
3439:
3432:
3425:
3417:
3411:
3409:
3408:
3403:
3401:
3394:
3393:
3377:
3376:
3364:
3363:
3347:
3346:
3330:
3329:
3320:
3311:
3305:
3304:
3284:
3275:
3266:
3257:
3253:
3244:
3237:
3235:
3234:
3231:
3228:
3220:
3211:
3200:
3198:
3197:
3192:
3190:
3186:
3101:
3099:
3098:
3093:
3091:
3087:
3086:
3070:
3069:
3060:
3051:
3044:
3043:
3027:
3026:
3014:
3013:
2992:
2990:
2989:
2984:
2982:
2979:
2969:
2964:
2951:
2947:
2944:
2937:
2932:
2927:
2915:
2912:
2905:
2900:
2895:
2891:
2869:
2867:
2866:
2861:
2859:
2855:
2770:
2768:
2767:
2762:
2760:
2756:
2755:
2739:
2738:
2722:
2721:
2705:
2704:
2680:
2678:
2677:
2672:
2670:
2667:
2657:
2652:
2639:
2638:
2637:
2634:
2627:
2622:
2617:
2608:
2607:
2604:
2597:
2592:
2587:
2577:
2572:
2546:
2544:
2543:
2538:
2536:
2532:
2503:
2495:
2486:
2478:
2433:
2431:
2430:
2425:
2423:
2419:
2418:
2402:
2401:
2392:
2383:
2377:
2376:
2363:
2362:
2346:
2345:
2333:
2332:
2311:
2309:
2308:
2303:
2301:
2298:
2293:
2288:
2277:
2272:
2267:
2266:
2265:
2262:
2260:
2251:
2248:
2243:
2238:
2237:
2232:
2223:
2219:
2218:
2215:
2210:
2205:
2200:
2199:
2192:
2187:
2156:
2154:
2153:
2148:
2146:
2142:
2108:
2100:
2096:
2088:
2040:
2038:
2037:
2032:
2030:
2029:
2017:
2016:
1998:
1997:
1980:
1978:
1977:
1972:
1970:
1967:
1960:
1955:
1942:
1941:
1940:
1939:
1936:
1929:
1924:
1915:
1906:
1901:
1896:
1887:
1878:
1874:
1873:
1870:
1863:
1858:
1847:
1842:
1831:
1826:
1800:
1798:
1797:
1792:
1790:
1786:
1755:
1747:
1743:
1735:
1687:
1685:
1684:
1679:
1677:
1673:
1672:
1656:
1655:
1643:
1642:
1629:
1628:
1612:
1611:
1602:
1593:
1587:
1586:
1565:
1563:
1562:
1557:
1555:
1552:
1545:
1540:
1529:
1524:
1511:
1510:
1507:
1500:
1495:
1486:
1477:
1472:
1467:
1458:
1449:
1445:
1444:
1441:
1434:
1429:
1418:
1413:
1402:
1397:
1371:
1369:
1368:
1363:
1361:
1357:
1255:
1253:
1252:
1247:
1245:
1242:
1232:
1227:
1213:
1208:
1197:
1192:
1174:
1164:
1159:
1145:
1140:
1129:
1124:
1106:
1099:
1094:
1083:
1078:
1067:
1062:
1027:
1017:
1008:
1004:
995:
990:augmented matrix
985:
983:
982:
977:
975:
968:
967:
942:
937:
923:
918:
907:
902:
880:
879:
854:
849:
835:
830:
819:
814:
792:
791:
769:
764:
753:
748:
737:
732:
694:
692:
691:
686:
681:
680:
645:
644:
609:
608:
560:Row echelon form
521:LU decomposition
517:Frobenius matrix
481:
480:
472:
470:
469:
464:
462:
461:
375:
374:
285:
284:
195:
194:
102:row echelon form
42:, also known as
38:In mathematics,
21:
6857:
6856:
6852:
6851:
6850:
6848:
6847:
6846:
6827:
6826:
6825:
6820:
6802:
6764:
6720:
6657:
6609:
6551:
6542:
6508:Change of basis
6498:Multilinear map
6436:
6418:
6413:
6376:
6371:
6364:
6362:
6355:
6338:
6333:
6316:
6309:
6302:
6297:
6291:
6274:
6268:
6248:
6233:
6228:
6190:
6184:
6164:
6155:
6149:
6136:
6130:
6113:
6107:
6090:
6084:
6067:
6063:
6058:
6057:
6035:
6034:
6030:
6010:
6009:
6005:
5997:
5993:
5979:
5945:
5944:
5937:
5930:
5905:
5904:
5900:
5892:
5888:
5866:10.2307/2322413
5849:
5848:
5844:
5836:
5832:
5824:
5820:
5812:
5808:
5800:
5796:
5789:
5774:
5773:
5769:
5761:
5757:
5748:
5746:
5738:
5737:
5733:
5728:
5710:
5687:
5678:*/
5623:h := 1 /*
5613:
5609:
5605:
5601:
5586:
5576:
5573:
5554:
5526:
5524:Generalizations
5502:
5415:
5395:
5394:
5388:soft O notation
5360:
5340:
5339:
5284:
5273:
5257:
5244:
5228:
5227:
5220:
5219:
5198:
5193:
5192:
5165:
5160:
5159:
5138:
5133:
5132:
5105:
5100:
5099:
5072:
5067:
5066:
5036:
5015:
5010:
5009:
4988:
4983:
4982:
4961:
4956:
4955:
4934:
4929:
4928:
4914:
4908:
4879:
4871:
4835:
4832:time complexity
4819:
4803:
4787:
4776:
4770:
4764:
4757:
4745:
4741:
4719:
4715:
4707:
4703:
4695:
4691:
4669:
4648:
4647:
4642:
4637:
4632:
4627:
4622:
4617:
4612:
4607:
4601:
4600:
4595:
4590:
4585:
4580:
4575:
4570:
4565:
4560:
4554:
4553:
4548:
4543:
4538:
4533:
4528:
4523:
4518:
4513:
4507:
4506:
4501:
4496:
4491:
4486:
4481:
4476:
4471:
4466:
4460:
4459:
4454:
4449:
4444:
4439:
4434:
4429:
4424:
4419:
4413:
4412:
4407:
4402:
4397:
4392:
4387:
4382:
4377:
4372:
4362:
4350:
4349:
4345:
4335:
4332:
4317:
4307:
4297:
4291:
4264:
4263:
4251:
4239:
4227:
4222:
4217:
4211:
4210:
4198:
4193:
4181:
4176:
4171:
4165:
4164:
4152:
4140:
4128:
4123:
4118:
4107:
4082:
4081:
4058:
4057:
4052:
4047:
4042:
4037:
4029:
4023:
4022:
4017:
4012:
4007:
3999:
3994:
3985:
3984:
3979:
3974:
3969:
3964:
3956:
3945:
3920:
3919:
3896:
3895:
3890:
3882:
3876:
3875:
3867:
3862:
3853:
3852:
3847:
3839:
3829:
3817:
3816:
3807:
3801:
3795:
3789:
3783:
3773:
3760:
3754:
3751:identity matrix
3741:
3727:
3721:
3718:
3712:
3701:
3689:
3649:
3648:
3634:
3624:
3583:
3561:
3560:
3556:
3552:
3548:
3544:
3540:
3536:
3519:
3511:
3458:Chapter Eight:
3454:
3434:
3427:
3420:
3415:
3399:
3398:
3385:
3378:
3368:
3355:
3352:
3351:
3338:
3331:
3321:
3296:
3287:
3286:
3283:
3277:
3274:
3268:
3265:
3259:
3255:
3252:
3246:
3243:
3232:
3229:
3226:
3225:
3223:
3222:
3219:
3213:
3209:
3184:
3183:
3175:
3170:
3165:
3159:
3158:
3153:
3148:
3143:
3137:
3136:
3131:
3126:
3121:
3110:
3105:
3104:
3089:
3088:
3078:
3071:
3061:
3046:
3045:
3035:
3028:
3018:
3005:
2996:
2995:
2980:
2978:
2970:
2959:
2954:
2950:
2945:
2943:
2938:
2926:
2923:
2918:
2913:
2911:
2906:
2894:
2890:
2887:
2875:
2874:
2853:
2852:
2844:
2839:
2834:
2828:
2827:
2822:
2817:
2812:
2806:
2805:
2800:
2795:
2790:
2779:
2774:
2773:
2758:
2757:
2747:
2740:
2730:
2724:
2723:
2713:
2706:
2696:
2684:
2683:
2668:
2666:
2658:
2647:
2642:
2635:
2633:
2628:
2616:
2613:
2605:
2603:
2598:
2586:
2583:
2578:
2567:
2552:
2551:
2530:
2529:
2524:
2516:
2511:
2505:
2504:
2492:
2487:
2475:
2469:
2468:
2463:
2458:
2453:
2442:
2437:
2436:
2421:
2420:
2410:
2403:
2393:
2368:
2365:
2364:
2354:
2347:
2337:
2324:
2315:
2314:
2299:
2297:
2283:
2278:
2263:
2261:
2236:
2216:
2214:
2198:
2193:
2182:
2167:
2166:
2140:
2139:
2134:
2126:
2121:
2115:
2114:
2109:
2097:
2085:
2079:
2078:
2073:
2065:
2060:
2049:
2044:
2043:
2021:
2008:
1989:
1984:
1983:
1968:
1966:
1961:
1950:
1937:
1935:
1930:
1919:
1902:
1891:
1871:
1869:
1864:
1853:
1848:
1837:
1832:
1821:
1806:
1805:
1784:
1783:
1778:
1773:
1768:
1762:
1761:
1756:
1744:
1732:
1726:
1725:
1720:
1712:
1707:
1696:
1691:
1690:
1675:
1674:
1664:
1657:
1647:
1634:
1631:
1630:
1620:
1613:
1603:
1578:
1569:
1568:
1553:
1551:
1546:
1535:
1530:
1519:
1508:
1506:
1501:
1490:
1473:
1462:
1442:
1440:
1435:
1424:
1419:
1408:
1403:
1392:
1377:
1376:
1355:
1354:
1346:
1341:
1336:
1327:
1326:
1318:
1313:
1305:
1296:
1295:
1290:
1282:
1277:
1266:
1261:
1260:
1243:
1241:
1233:
1222:
1214:
1203:
1198:
1187:
1175:
1173:
1165:
1154:
1146:
1135:
1130:
1119:
1107:
1105:
1100:
1089:
1084:
1073:
1068:
1057:
1042:
1041:
1020:triangular form
1016:
1010:
1006:
1003:
997:
993:
973:
972:
959:
951:
943:
932:
924:
913:
908:
897:
885:
884:
871:
863:
855:
844:
836:
825:
820:
809:
797:
796:
783:
775:
770:
759:
754:
743:
738:
727:
712:
711:
708:
675:
674:
669:
664:
659:
653:
652:
647:
636:
631:
625:
624:
616:
611:
600:
590:
584:
583:
562:
556:
529:
494:
478:
477:
456:
455:
450:
445:
440:
434:
433:
428:
423:
418:
412:
411:
403:
395:
390:
380:
369:
368:
363:
358:
353:
347:
346:
338:
330:
322:
316:
315:
310:
305:
300:
290:
279:
278:
273:
268:
263:
257:
256:
248:
240:
232:
226:
225:
220:
215:
210:
200:
189:
188:
183:
178:
173:
167:
166:
161:
153:
148:
142:
141:
136:
131:
126:
116:
110:
109:
28:
23:
22:
15:
12:
11:
5:
6855:
6853:
6845:
6844:
6839:
6829:
6828:
6822:
6821:
6819:
6818:
6807:
6804:
6803:
6801:
6800:
6795:
6790:
6785:
6780:
6778:Floating-point
6774:
6772:
6766:
6765:
6763:
6762:
6760:Tensor product
6757:
6752:
6747:
6745:Function space
6742:
6737:
6731:
6729:
6722:
6721:
6719:
6718:
6713:
6708:
6703:
6698:
6693:
6688:
6683:
6681:Triple product
6678:
6673:
6667:
6665:
6659:
6658:
6656:
6655:
6650:
6645:
6640:
6635:
6630:
6625:
6619:
6617:
6611:
6610:
6608:
6607:
6602:
6597:
6595:Transformation
6592:
6587:
6585:Multiplication
6582:
6577:
6572:
6567:
6561:
6559:
6553:
6552:
6545:
6543:
6541:
6540:
6535:
6530:
6525:
6520:
6515:
6510:
6505:
6500:
6495:
6490:
6485:
6480:
6475:
6470:
6465:
6460:
6455:
6450:
6444:
6442:
6441:Basic concepts
6438:
6437:
6435:
6434:
6429:
6423:
6420:
6419:
6416:Linear algebra
6414:
6412:
6411:
6404:
6397:
6389:
6383:
6382:
6375:
6374:External links
6372:
6370:
6369:
6353:
6336:
6331:
6314:
6295:
6289:
6281:Addison-Wesley
6272:
6266:
6246:
6226:
6199:(2): 163–218,
6188:
6182:
6166:Golub, Gene H.
6162:
6153:
6147:
6134:
6128:
6111:
6105:
6088:
6083:978-0471624899
6082:
6064:
6062:
6059:
6056:
6055:
6028:
6003:
5991:
5977:
5951:Lovász, László
5935:
5928:
5898:
5886:
5842:
5830:
5818:
5806:
5794:
5787:
5767:
5755:
5730:
5729:
5727:
5724:
5723:
5722:
5716:
5709:
5706:
5691:absolute value
5622:
5572:
5569:
5563:(matrices are
5544:monomial order
5525:
5522:
5501:
5498:
5497:
5496:
5491:Computing the
5489:
5486:inverse matrix
5484:Computing the
5482:
5472:
5467:Computing the
5465:
5448:Hensel lifting
5427:
5422:
5418:
5414:
5408:
5405:
5375:
5372:
5367:
5363:
5359:
5353:
5350:
5316:
5309:
5306:
5303:
5300:
5297:
5294:
5291:
5287:
5280:
5276:
5270:
5267:
5264:
5260:
5256:
5251:
5247:
5241:
5238:
5235:
5231:
5205:
5201:
5188:respectively.
5177:
5172:
5168:
5145:
5141:
5118:
5115:
5112:
5108:
5085:
5082:
5079:
5075:
5054:
5049:
5046:
5043:
5039:
5034:
5028:
5025:
5022:
5018:
4995:
4991:
4981:a multiple of
4968:
4964:
4941:
4937:
4910:Main article:
4907:
4904:
4864:bit complexity
4769:equations for
4759:The number of
4756:
4753:
4657:
4652:
4646:
4643:
4641:
4638:
4636:
4633:
4631:
4628:
4626:
4623:
4621:
4618:
4616:
4613:
4611:
4608:
4606:
4603:
4602:
4599:
4596:
4594:
4591:
4589:
4586:
4584:
4581:
4579:
4576:
4574:
4571:
4569:
4566:
4564:
4561:
4559:
4556:
4555:
4552:
4549:
4547:
4544:
4542:
4539:
4537:
4534:
4532:
4529:
4527:
4524:
4522:
4519:
4517:
4514:
4512:
4509:
4508:
4505:
4502:
4500:
4497:
4495:
4492:
4490:
4487:
4485:
4482:
4480:
4477:
4475:
4472:
4470:
4467:
4465:
4462:
4461:
4458:
4455:
4453:
4450:
4448:
4445:
4443:
4440:
4438:
4435:
4433:
4430:
4428:
4425:
4423:
4420:
4418:
4415:
4414:
4411:
4408:
4406:
4403:
4401:
4398:
4396:
4393:
4391:
4388:
4386:
4383:
4381:
4378:
4376:
4373:
4371:
4368:
4367:
4365:
4360:
4357:
4331:
4328:
4290:. Denoting by
4273:
4269:
4260:
4257:
4252:
4248:
4245:
4240:
4236:
4233:
4228:
4226:
4223:
4221:
4218:
4216:
4213:
4212:
4207:
4204:
4199:
4197:
4194:
4190:
4187:
4182:
4180:
4177:
4175:
4172:
4170:
4167:
4166:
4161:
4158:
4153:
4149:
4146:
4141:
4137:
4134:
4129:
4127:
4124:
4122:
4119:
4117:
4114:
4113:
4110:
4106:
4103:
4100:
4096:
4092:
4089:
4067:
4063:
4056:
4053:
4051:
4048:
4046:
4043:
4041:
4038:
4036:
4033:
4030:
4028:
4025:
4024:
4021:
4018:
4016:
4013:
4011:
4008:
4006:
4003:
4000:
3998:
3995:
3993:
3990:
3987:
3986:
3983:
3980:
3978:
3975:
3973:
3970:
3968:
3965:
3963:
3960:
3957:
3955:
3952:
3951:
3948:
3944:
3941:
3938:
3934:
3930:
3927:
3905:
3900:
3894:
3891:
3889:
3886:
3883:
3881:
3878:
3877:
3874:
3871:
3868:
3866:
3863:
3861:
3858:
3855:
3854:
3851:
3848:
3846:
3843:
3840:
3838:
3835:
3834:
3832:
3827:
3824:
3738:inverse matrix
3711:
3708:
3669:
3666:
3663:
3659:
3656:
3610:
3605:
3601:
3598:
3595:
3592:
3589:
3586:
3580:
3577:
3574:
3571:
3568:
3533:
3532:
3529:
3526:
3518:
3515:
3510:
3507:
3503:Wilhelm Jordan
3491:hand computers
3453:
3450:
3397:
3392:
3388:
3384:
3381:
3379:
3375:
3371:
3367:
3362:
3358:
3354:
3353:
3350:
3345:
3341:
3337:
3334:
3332:
3328:
3324:
3317:
3314:
3308:
3303:
3299:
3295:
3294:
3281:
3272:
3263:
3250:
3241:
3217:
3206:
3205:
3202:
3201:
3189:
3182:
3179:
3176:
3174:
3171:
3169:
3166:
3164:
3161:
3160:
3157:
3154:
3152:
3149:
3147:
3144:
3142:
3139:
3138:
3135:
3132:
3130:
3127:
3125:
3122:
3120:
3117:
3116:
3113:
3102:
3085:
3081:
3077:
3074:
3072:
3068:
3064:
3057:
3054:
3048:
3047:
3042:
3038:
3034:
3031:
3029:
3025:
3021:
3017:
3012:
3008:
3004:
3003:
2993:
2977:
2974:
2971:
2967:
2962:
2960:
2958:
2955:
2952:
2948:
2946:
2942:
2939:
2935:
2930:
2928:
2924:
2922:
2919:
2916:
2914:
2910:
2907:
2903:
2898:
2896:
2892:
2888:
2886:
2883:
2882:
2871:
2870:
2858:
2851:
2848:
2845:
2843:
2840:
2838:
2835:
2833:
2830:
2829:
2826:
2823:
2821:
2818:
2816:
2813:
2811:
2808:
2807:
2804:
2801:
2799:
2796:
2794:
2791:
2789:
2786:
2785:
2782:
2771:
2754:
2750:
2746:
2743:
2741:
2737:
2733:
2729:
2726:
2725:
2720:
2716:
2712:
2709:
2707:
2703:
2699:
2695:
2692:
2691:
2681:
2665:
2662:
2659:
2655:
2650:
2648:
2646:
2643:
2640:
2636:
2632:
2629:
2625:
2620:
2618:
2614:
2612:
2609:
2606:
2602:
2599:
2595:
2590:
2588:
2584:
2582:
2579:
2575:
2570:
2568:
2566:
2563:
2560:
2559:
2548:
2547:
2535:
2528:
2525:
2523:
2520:
2517:
2515:
2512:
2510:
2507:
2506:
2501:
2498:
2493:
2491:
2488:
2484:
2481:
2476:
2474:
2471:
2470:
2467:
2464:
2462:
2459:
2457:
2454:
2452:
2449:
2448:
2445:
2434:
2417:
2413:
2409:
2406:
2404:
2400:
2396:
2389:
2386:
2380:
2375:
2371:
2367:
2366:
2361:
2357:
2353:
2350:
2348:
2344:
2340:
2336:
2331:
2327:
2323:
2322:
2312:
2296:
2291:
2286:
2284:
2282:
2279:
2275:
2270:
2268:
2264:
2257:
2254:
2246:
2241:
2239:
2235:
2229:
2226:
2220:
2217:
2213:
2208:
2203:
2201:
2197:
2194:
2190:
2185:
2183:
2181:
2178:
2175:
2174:
2163:
2162:
2158:
2157:
2145:
2138:
2135:
2133:
2130:
2127:
2125:
2122:
2120:
2117:
2116:
2113:
2110:
2106:
2103:
2098:
2094:
2091:
2086:
2084:
2081:
2080:
2077:
2074:
2072:
2069:
2066:
2064:
2061:
2059:
2056:
2055:
2052:
2041:
2028:
2024:
2020:
2015:
2011:
2007:
2004:
2001:
1996:
1992:
1981:
1965:
1962:
1958:
1953:
1951:
1949:
1946:
1943:
1938:
1934:
1931:
1927:
1922:
1920:
1918:
1912:
1909:
1903:
1899:
1894:
1892:
1890:
1884:
1881:
1875:
1872:
1868:
1865:
1861:
1856:
1854:
1852:
1849:
1845:
1840:
1838:
1836:
1833:
1829:
1824:
1822:
1820:
1817:
1814:
1813:
1802:
1801:
1789:
1782:
1779:
1777:
1774:
1772:
1769:
1767:
1764:
1763:
1760:
1757:
1753:
1750:
1745:
1741:
1738:
1733:
1731:
1728:
1727:
1724:
1721:
1719:
1716:
1713:
1711:
1708:
1706:
1703:
1702:
1699:
1688:
1671:
1667:
1663:
1660:
1658:
1654:
1650:
1646:
1641:
1637:
1633:
1632:
1627:
1623:
1619:
1616:
1614:
1610:
1606:
1599:
1596:
1590:
1585:
1581:
1577:
1576:
1566:
1550:
1547:
1543:
1538:
1536:
1534:
1531:
1527:
1522:
1520:
1518:
1515:
1512:
1509:
1505:
1502:
1498:
1493:
1491:
1489:
1483:
1480:
1474:
1470:
1465:
1463:
1461:
1455:
1452:
1446:
1443:
1439:
1436:
1432:
1427:
1425:
1423:
1420:
1416:
1411:
1409:
1407:
1404:
1400:
1395:
1393:
1391:
1388:
1385:
1384:
1373:
1372:
1360:
1353:
1350:
1347:
1345:
1342:
1340:
1337:
1335:
1332:
1329:
1328:
1325:
1322:
1319:
1317:
1314:
1312:
1309:
1306:
1304:
1301:
1298:
1297:
1294:
1291:
1289:
1286:
1283:
1281:
1278:
1276:
1273:
1272:
1269:
1258:
1256:
1240:
1237:
1234:
1230:
1225:
1223:
1221:
1218:
1215:
1211:
1206:
1204:
1202:
1199:
1195:
1190:
1188:
1186:
1183:
1180:
1177:
1176:
1172:
1169:
1166:
1162:
1157:
1155:
1153:
1150:
1147:
1143:
1138:
1136:
1134:
1131:
1127:
1122:
1120:
1118:
1115:
1112:
1109:
1108:
1104:
1101:
1097:
1092:
1090:
1088:
1085:
1081:
1076:
1074:
1072:
1069:
1065:
1060:
1058:
1056:
1053:
1050:
1049:
1038:
1037:
1034:
1033:Row operations
1031:
1014:
1001:
971:
966:
962:
958:
954:
952:
950:
947:
944:
940:
935:
933:
931:
928:
925:
921:
916:
914:
912:
909:
905:
900:
898:
896:
893:
890:
887:
886:
883:
878:
874:
870:
866:
864:
862:
859:
856:
852:
847:
845:
843:
840:
837:
833:
828:
826:
824:
821:
817:
812:
810:
808:
805:
802:
799:
798:
795:
790:
786:
782:
778:
776:
774:
771:
767:
762:
760:
758:
755:
751:
746:
744:
742:
739:
735:
730:
728:
726:
723:
720:
719:
707:
704:
684:
679:
673:
670:
668:
665:
663:
660:
658:
655:
654:
651:
648:
643:
637:
635:
632:
630:
627:
626:
623:
620:
617:
615:
612:
607:
601:
599:
596:
595:
593:
558:Main article:
555:
552:
547:
546:
543:
536:
528:
527:Row operations
525:
493:
490:
460:
454:
451:
449:
446:
444:
441:
439:
436:
435:
432:
429:
427:
424:
422:
419:
417:
414:
413:
410:
407:
404:
402:
399:
396:
394:
391:
389:
386:
385:
383:
378:
373:
367:
364:
362:
359:
357:
354:
352:
349:
348:
345:
342:
339:
337:
334:
331:
329:
326:
323:
321:
318:
317:
314:
311:
309:
306:
304:
301:
299:
296:
295:
293:
288:
283:
277:
274:
272:
269:
267:
264:
262:
259:
258:
255:
252:
249:
247:
244:
241:
239:
236:
233:
231:
228:
227:
224:
221:
219:
216:
214:
211:
209:
206:
205:
203:
198:
193:
187:
184:
182:
179:
177:
174:
172:
169:
168:
165:
162:
160:
157:
154:
152:
149:
147:
144:
143:
140:
137:
135:
132:
130:
127:
125:
122:
121:
119:
94:
93:
90:
87:
26:
24:
18:Row reductions
14:
13:
10:
9:
6:
4:
3:
2:
6854:
6843:
6840:
6838:
6835:
6834:
6832:
6817:
6809:
6808:
6805:
6799:
6796:
6794:
6793:Sparse matrix
6791:
6789:
6786:
6784:
6781:
6779:
6776:
6775:
6773:
6771:
6767:
6761:
6758:
6756:
6753:
6751:
6748:
6746:
6743:
6741:
6738:
6736:
6733:
6732:
6730:
6728:constructions
6727:
6723:
6717:
6716:Outermorphism
6714:
6712:
6709:
6707:
6704:
6702:
6699:
6697:
6694:
6692:
6689:
6687:
6684:
6682:
6679:
6677:
6676:Cross product
6674:
6672:
6669:
6668:
6666:
6664:
6660:
6654:
6651:
6649:
6646:
6644:
6643:Outer product
6641:
6639:
6636:
6634:
6631:
6629:
6626:
6624:
6623:Orthogonality
6621:
6620:
6618:
6616:
6612:
6606:
6603:
6601:
6600:Cramer's rule
6598:
6596:
6593:
6591:
6588:
6586:
6583:
6581:
6578:
6576:
6573:
6571:
6570:Decomposition
6568:
6566:
6563:
6562:
6560:
6558:
6554:
6549:
6539:
6536:
6534:
6531:
6529:
6526:
6524:
6521:
6519:
6516:
6514:
6511:
6509:
6506:
6504:
6501:
6499:
6496:
6494:
6491:
6489:
6486:
6484:
6481:
6479:
6476:
6474:
6471:
6469:
6466:
6464:
6461:
6459:
6456:
6454:
6451:
6449:
6446:
6445:
6443:
6439:
6433:
6430:
6428:
6425:
6424:
6421:
6417:
6410:
6405:
6403:
6398:
6396:
6391:
6390:
6387:
6381:
6378:
6377:
6373:
6361:on 2012-03-19
6360:
6356:
6350:
6346:
6342:
6341:"Section 2.2"
6337:
6334:
6328:
6324:
6320:
6315:
6308:
6301:
6296:
6292:
6286:
6282:
6278:
6273:
6269:
6263:
6259:
6255:
6251:
6247:
6243:
6239:
6232:
6227:
6224:
6220:
6216:
6212:
6207:
6202:
6198:
6194:
6189:
6185:
6179:
6175:
6171:
6167:
6163:
6159:
6154:
6150:
6144:
6140:
6135:
6131:
6125:
6121:
6120:Prentice Hall
6117:
6112:
6108:
6102:
6098:
6094:
6089:
6085:
6079:
6075:
6071:
6066:
6065:
6060:
6051:
6047:
6043:
6039:
6032:
6029:
6023:
6018:
6014:
6013:Lim, Lek-Heng
6007:
6004:
6000:
5995:
5992:
5988:
5984:
5980:
5974:
5970:
5966:
5962:
5961:
5956:
5952:
5948:
5942:
5940:
5936:
5931:
5929:0-89791-875-4
5925:
5921:
5917:
5913:
5909:
5902:
5899:
5895:
5890:
5887:
5883:
5879:
5875:
5871:
5867:
5863:
5859:
5855:
5854:
5846:
5843:
5840:, p. 789
5839:
5834:
5831:
5827:
5822:
5819:
5815:
5810:
5807:
5803:
5798:
5795:
5790:
5784:
5780:
5779:
5771:
5768:
5764:
5763:Calinger 1999
5759:
5756:
5745:
5741:
5735:
5732:
5725:
5720:
5717:
5715:
5712:
5711:
5707:
5705:
5702:
5700:
5696:
5692:
5685:
5681:
5677:
5673:
5669:
5665:
5661:
5658:
5654:
5650:
5646:
5642:
5639:k ≤ n /*
5638:
5634:
5630:
5626:
5621:
5619:
5599:
5594:
5592:
5583:
5579:
5570:
5568:
5566:
5562:
5557:
5552:
5547:
5545:
5541:
5537:
5533:
5531:
5523:
5521:
5519:
5515:
5511:
5507:
5499:
5494:
5490:
5487:
5483:
5481:
5477:
5473:
5470:
5466:
5464:
5460:
5456:
5455:
5454:
5451:
5449:
5445:
5441:
5420:
5416:
5403:
5391:
5389:
5373:
5365:
5361:
5348:
5337:
5331:
5328:
5314:
5307:
5304:
5301:
5298:
5295:
5292:
5289:
5285:
5278:
5274:
5268:
5265:
5262:
5258:
5254:
5249:
5245:
5239:
5236:
5233:
5229:
5203:
5199:
5189:
5175:
5170:
5166:
5143:
5139:
5116:
5113:
5110:
5106:
5083:
5080:
5077:
5073:
5052:
5047:
5044:
5041:
5037:
5032:
5026:
5023:
5020:
5016:
4993:
4989:
4966:
4962:
4939:
4935:
4925:
4923:
4919:
4913:
4905:
4903:
4901:
4897:
4891:
4889:
4883:
4875:
4869:
4865:
4861:
4857:
4853:
4849:
4843:
4839:
4833:
4829:
4823:
4815:
4811:
4807:
4799:
4795:
4791:
4783:
4779:
4773:
4767:
4762:
4754:
4752:
4749:
4738:
4734:
4730:
4726:
4722:
4713:
4701:
4688:
4684:
4680:
4676:
4672:
4655:
4650:
4644:
4639:
4634:
4629:
4624:
4619:
4614:
4609:
4604:
4597:
4592:
4587:
4582:
4577:
4572:
4567:
4562:
4557:
4550:
4545:
4540:
4535:
4530:
4525:
4520:
4515:
4510:
4503:
4498:
4493:
4488:
4483:
4478:
4473:
4468:
4463:
4456:
4451:
4446:
4441:
4436:
4431:
4426:
4421:
4416:
4409:
4404:
4399:
4394:
4389:
4384:
4379:
4374:
4369:
4363:
4358:
4355:
4342:
4338:
4329:
4327:
4324:
4320:
4314:
4310:
4304:
4300:
4294:
4289:
4284:
4271:
4267:
4258:
4255:
4246:
4243:
4234:
4231:
4224:
4219:
4214:
4205:
4202:
4195:
4188:
4185:
4178:
4173:
4168:
4159:
4156:
4147:
4144:
4135:
4132:
4125:
4120:
4115:
4108:
4104:
4098:
4090:
4078:
4065:
4061:
4054:
4049:
4044:
4039:
4034:
4031:
4026:
4019:
4014:
4009:
4004:
4001:
3996:
3991:
3988:
3981:
3976:
3971:
3966:
3961:
3958:
3953:
3946:
3942:
3936:
3928:
3916:
3903:
3898:
3892:
3887:
3884:
3879:
3872:
3869:
3864:
3859:
3856:
3849:
3844:
3841:
3836:
3830:
3825:
3822:
3813:
3810:
3804:
3798:
3792:
3786:
3780:
3776:
3771:
3767:
3763:
3759:, forming an
3757:
3752:
3748:
3744:
3739:
3734:
3730:
3724:
3717:
3709:
3707:
3704:
3693:
3687:
3664:
3661:
3657:
3646:
3641:
3639:
3631:
3627:
3621:
3608:
3603:
3596:
3590:
3587:
3584:
3578:
3572:
3530:
3527:
3524:
3523:
3522:
3516:
3514:
3508:
3506:
3504:
3499:
3494:
3492:
3488:
3483:
3479:
3474:
3472:
3468:
3467:
3462:
3461:
3451:
3449:
3446:
3441:
3437:
3430:
3423:
3412:
3395:
3390:
3386:
3380:
3373:
3369:
3365:
3360:
3356:
3348:
3343:
3339:
3333:
3326:
3322:
3315:
3312:
3306:
3301:
3297:
3280:
3271:
3262:
3249:
3240:
3216:
3187:
3180:
3177:
3172:
3167:
3162:
3155:
3150:
3145:
3140:
3133:
3128:
3123:
3118:
3111:
3103:
3083:
3079:
3073:
3066:
3062:
3055:
3052:
3040:
3036:
3030:
3023:
3019:
3015:
3010:
3006:
2994:
2975:
2972:
2965:
2961:
2956:
2940:
2933:
2929:
2920:
2908:
2901:
2897:
2884:
2873:
2856:
2849:
2846:
2841:
2836:
2831:
2824:
2819:
2814:
2809:
2802:
2797:
2792:
2787:
2780:
2772:
2752:
2748:
2742:
2735:
2731:
2727:
2718:
2714:
2708:
2701:
2697:
2693:
2682:
2663:
2660:
2653:
2649:
2644:
2630:
2623:
2619:
2610:
2600:
2593:
2589:
2580:
2573:
2569:
2564:
2561:
2550:
2533:
2526:
2521:
2518:
2513:
2508:
2499:
2496:
2489:
2482:
2479:
2472:
2465:
2460:
2455:
2450:
2443:
2435:
2415:
2411:
2405:
2398:
2394:
2387:
2384:
2378:
2373:
2369:
2359:
2355:
2349:
2342:
2338:
2334:
2329:
2325:
2313:
2294:
2289:
2285:
2280:
2273:
2269:
2255:
2252:
2244:
2240:
2233:
2227:
2224:
2211:
2206:
2202:
2195:
2188:
2184:
2179:
2176:
2165:
2159:
2143:
2136:
2131:
2128:
2123:
2118:
2111:
2104:
2101:
2092:
2089:
2082:
2075:
2070:
2067:
2062:
2057:
2050:
2042:
2026:
2022:
2013:
2009:
2005:
2002:
1999:
1994:
1990:
1982:
1963:
1956:
1952:
1947:
1944:
1932:
1925:
1921:
1916:
1910:
1907:
1897:
1893:
1888:
1882:
1879:
1866:
1859:
1855:
1850:
1843:
1839:
1834:
1827:
1823:
1818:
1815:
1804:
1787:
1780:
1775:
1770:
1765:
1758:
1751:
1748:
1739:
1736:
1729:
1722:
1717:
1714:
1709:
1704:
1697:
1689:
1669:
1665:
1659:
1652:
1648:
1644:
1639:
1635:
1625:
1621:
1615:
1608:
1604:
1597:
1594:
1588:
1583:
1579:
1567:
1548:
1541:
1537:
1532:
1525:
1521:
1516:
1513:
1503:
1496:
1492:
1487:
1481:
1478:
1468:
1464:
1459:
1453:
1450:
1437:
1430:
1426:
1421:
1414:
1410:
1405:
1398:
1394:
1389:
1386:
1375:
1358:
1351:
1348:
1343:
1338:
1333:
1330:
1323:
1320:
1315:
1310:
1307:
1302:
1299:
1292:
1287:
1284:
1279:
1274:
1267:
1259:
1257:
1238:
1235:
1228:
1224:
1219:
1216:
1209:
1205:
1200:
1193:
1189:
1184:
1181:
1178:
1170:
1167:
1160:
1156:
1151:
1148:
1141:
1137:
1132:
1125:
1121:
1116:
1113:
1110:
1102:
1095:
1091:
1086:
1079:
1075:
1070:
1063:
1059:
1054:
1051:
1040:
1035:
1032:
1029:
1028:
1025:
1024:
1023:
1021:
1013:
1000:
991:
986:
964:
960:
953:
948:
945:
938:
934:
929:
926:
919:
915:
910:
903:
899:
894:
891:
888:
876:
872:
865:
860:
857:
850:
846:
841:
838:
831:
827:
822:
815:
811:
806:
803:
800:
788:
784:
777:
772:
765:
761:
756:
749:
745:
740:
733:
729:
724:
721:
705:
703:
699:
695:
682:
677:
671:
666:
661:
656:
649:
633:
628:
621:
618:
613:
597:
591:
580:
577:
573:
569:
568:
561:
553:
551:
544:
541:
537:
534:
533:
532:
526:
524:
522:
518:
514:
510:
505:
503:
499:
491:
489:
486:
482:
473:
458:
452:
447:
442:
437:
430:
425:
420:
415:
408:
405:
400:
397:
392:
387:
381:
371:
365:
360:
355:
350:
343:
340:
335:
332:
327:
324:
319:
312:
307:
302:
297:
291:
281:
275:
270:
265:
260:
253:
250:
245:
242:
237:
234:
229:
222:
217:
212:
207:
201:
191:
185:
180:
175:
170:
163:
158:
155:
150:
145:
138:
133:
128:
123:
117:
107:
103:
99:
91:
88:
85:
84:
83:
81:
77:
73:
69:
68:square matrix
65:
61:
57:
53:
49:
45:
44:row reduction
41:
32:
19:
6726:Vector space
6604:
6458:Vector space
6363:, retrieved
6359:the original
6344:
6321:, New York:
6318:
6276:
6253:
6244:(6): 782–792
6241:
6237:
6196:
6192:
6173:
6157:
6138:
6115:
6092:
6069:
6042:SpringerLink
6041:
6031:
6006:
5994:
5959:
5911:
5901:
5896:, p. 12
5889:
5857:
5851:
5845:
5833:
5821:
5809:
5797:
5777:
5770:
5758:
5747:. Retrieved
5743:
5734:
5703:
5694:
5688:
5683:
5679:
5675:
5671:
5667:
5663:
5659:
5656:
5652:
5648:
5640:
5636:
5632:
5628:
5624:
5617:
5595:
5581:
5577:
5574:
5548:
5534:
5527:
5503:
5479:
5475:
5458:
5452:
5392:
5332:
5329:
5190:
4926:
4922:Jack Edmonds
4915:
4892:
4890:complexity.
4881:
4873:
4852:finite field
4844:
4837:
4827:
4821:
4813:
4809:
4805:
4797:
4793:
4789:
4781:
4777:
4771:
4765:
4758:
4750:
4736:
4732:
4728:
4724:
4720:
4712:vector space
4686:
4682:
4678:
4674:
4670:
4340:
4336:
4333:
4322:
4318:
4312:
4308:
4302:
4298:
4292:
4285:
4079:
3917:
3814:
3808:
3802:
3796:
3790:
3784:
3778:
3774:
3770:block matrix
3765:
3761:
3755:
3746:
3742:
3732:
3728:
3722:
3719:
3702:
3691:
3637:
3629:
3625:
3622:
3534:
3520:
3512:
3509:Applications
3497:
3495:
3481:
3478:Isaac Newton
3475:
3464:
3459:
3455:
3444:
3442:
3435:
3428:
3421:
3419:solution is
3413:
3278:
3269:
3260:
3247:
3238:
3214:
3207:
1011:
998:
987:
709:
700:
696:
581:
571:
565:
563:
554:Echelon form
548:
530:
506:
495:
484:
476:
474:
95:
50:for solving
43:
39:
37:
6706:Multivector
6671:Determinant
6628:Dot product
6473:Linear span
6323:McGraw-Hill
6061:Works cited
5838:Grcar 2011b
5828:, p. 3
5814:Grcar 2011b
5802:Grcar 2011a
5744:www.emis.de
5666:*/
5612:and column
5469:determinant
4786:divisions,
3680:operations
64:determinant
6831:Categories
6740:Direct sum
6575:Invertible
6478:Linear map
6365:2011-08-08
5749:2022-12-02
5726:References
5598:pseudocode
5571:Pseudocode
4916:The first
3714:See also:
3706:above 20.
3267:by adding
3221:by adding
6770:Numerical
6533:Transpose
6206:0907.2397
6022:0911.1393
5874:0002-9890
5826:Lauritzen
5693:. Such a
5660:swap rows
5407:~
5352:~
5305:−
5293:−
5255:−
4551:∗
4546:∗
4504:∗
4499:∗
4494:∗
4489:∗
4484:∗
4457:∗
4452:∗
4447:∗
4442:∗
4437:∗
4432:∗
4410:∗
4405:∗
4400:∗
4395:∗
4390:∗
4385:∗
4380:∗
4375:∗
4032:−
4002:−
3989:−
3959:−
3885:−
3870:−
3857:−
3842:−
3688:requires
3647:requires
3591:
3585:∏
3383:→
3336:→
3178:−
3076:→
3033:→
3016:−
2973:−
2847:−
2745:→
2728:−
2711:→
2661:−
2519:−
2408:→
2352:→
2335:−
2274:−
2129:−
2068:−
2019:→
2003:−
1945:−
1844:−
1715:−
1662:→
1618:→
1415:−
1349:−
1331:−
1321:−
1308:−
1300:−
1285:−
1236:−
1179:−
1168:−
1126:−
1111:−
1080:−
946:−
889:−
858:−
816:−
801:−
750:−
619:−
406:−
398:−
377:→
341:−
333:−
325:−
287:→
251:−
243:−
235:−
197:→
156:−
48:algorithm
6816:Category
6755:Subspace
6750:Quotient
6701:Bivector
6615:Bilinear
6557:Matrices
6432:Glossary
6307:Archived
6252:(2002),
6223:14259511
6172:(1996),
6001:, §3.4.6
5957:(1993),
5708:See also
5618:in place
4856:integers
3254:. Next,
46:, is an
6427:Outline
5987:1261419
5882:2322413
5608:in row
5585:matrix
5561:tensors
5551:NP-hard
4344:matrix
3806:, then
3471:Liu Hui
3452:History
3445:reduced
3236:
3224:
6711:Tensor
6523:Kernel
6453:Vector
6448:Scalar
6351:
6329:
6287:
6264:
6221:
6180:
6145:
6126:
6103:
6080:
5985:
5975:
5926:
5880:
5872:
5785:
5645:argmax
5635:h ≤ m
5556:P ≠ NP
5386:using
5065:where
4784:+ 1)/2
4710:; the
4698:: the
3726:is an
3543:, let
3433:, and
576:type 3
540:scalar
56:matrix
6580:Minor
6565:Block
6503:Basis
6310:(PDF)
6303:(PDF)
6234:(PDF)
6219:S2CID
6201:arXiv
6017:arXiv
5878:JSTOR
5633:while
5565:array
5530:field
5218:with
3414:Once
572:pivot
66:of a
6735:Dual
6590:Rank
6349:ISBN
6327:ISBN
6285:ISBN
6262:ISBN
6258:SIAM
6178:ISBN
6143:ISBN
6124:ISBN
6101:ISBN
6078:ISBN
5973:ISBN
5924:ISBN
5870:ISSN
5783:ISBN
5657:else
5493:rank
5158:and
5098:and
4700:rank
3588:diag
3424:= −1
570:(or
60:rank
6211:doi
6046:doi
5965:doi
5916:doi
5862:doi
5680:for
5668:for
5637:and
5631:*/
5512:or
5446:or
5008:by
4902:).
4858:or
4816:)/6
4812:− 5
4808:+ 3
4800:)/6
4796:− 5
4792:+ 3
4740:in
4702:of
3777:× 2
3764:× 2
3567:det
3463:of
3438:= 2
3431:= 3
3276:to
3245:to
6833::
6343:,
6283:,
6279:,
6260:,
6242:58
6240:,
6236:,
6217:,
6209:,
6197:38
6195:,
6168:;
6122:,
6118:,
6099:,
6076:,
6044:.
6040:.
5983:MR
5981:,
5971:,
5953:;
5949:;
5938:^
5922:.
5910:.
5876:,
5868:,
5858:94
5856:,
5742:.
5649:if
5600:,
5593:.
5580:×
5478:=
5476:Ax
5450:.
5390:.
4880:O(
4872:O(
4842:.
4836:O(
4824:/3
4804:(2
4788:(2
4735:,
4731:,
4727:,
4723:,
4685:,
4681:,
4677:,
4673:,
4339:×
4321:=
4319:BI
4311:=
4301:=
4299:BA
3745:×
3731:×
3694:2)
3690:O(
3636:O(
3628:×
3559::
3426:,
1324:11
1171:11
861:11
186:35
176:11
6408:e
6401:t
6394:v
6294:.
6271:.
6213::
6203::
6187:.
6161:.
6152:.
6133:.
6110:.
6087:.
6052:.
6048::
6025:.
6019::
5967::
5932:.
5918::
5864::
5791:.
5752:.
5614:j
5610:i
5606:A
5602:A
5587:A
5582:n
5578:m
5480:b
5459:m
5426:)
5421:4
5417:n
5413:(
5404:O
5374:,
5371:)
5366:5
5362:n
5358:(
5349:O
5315:.
5308:1
5302:k
5299:,
5296:1
5290:k
5286:r
5279:k
5275:R
5269:k
5266:,
5263:i
5259:r
5250:i
5246:R
5240:k
5237:,
5234:k
5230:r
5204:i
5200:R
5176:,
5171:k
5167:R
5144:i
5140:R
5117:k
5114:,
5111:k
5107:r
5084:k
5081:,
5078:i
5074:r
5053:,
5048:k
5045:,
5042:k
5038:r
5033:/
5027:k
5024:,
5021:i
5017:r
4994:k
4990:R
4967:k
4963:R
4940:i
4936:R
4884:)
4882:n
4876:)
4874:n
4840:)
4838:n
4830:(
4822:n
4820:2
4814:n
4810:n
4806:n
4798:n
4794:n
4790:n
4782:n
4780:(
4778:n
4772:n
4766:n
4746:A
4742:T
4737:e
4733:d
4729:c
4725:b
4721:a
4716:A
4708:T
4704:A
4696:A
4692:T
4687:e
4683:d
4679:c
4675:b
4671:a
4656:,
4651:]
4645:0
4640:0
4635:0
4630:0
4625:0
4620:0
4615:0
4610:0
4605:0
4598:e
4593:0
4588:0
4583:0
4578:0
4573:0
4568:0
4563:0
4558:0
4541:d
4536:0
4531:0
4526:0
4521:0
4516:0
4511:0
4479:c
4474:0
4469:0
4464:0
4427:b
4422:0
4417:0
4370:a
4364:[
4359:=
4356:T
4346:A
4341:n
4337:m
4323:B
4313:A
4309:B
4303:I
4293:B
4272:.
4268:]
4259:4
4256:3
4247:2
4244:1
4235:4
4232:1
4225:1
4220:0
4215:0
4206:2
4203:1
4196:1
4189:2
4186:1
4179:0
4174:1
4169:0
4160:4
4157:1
4148:2
4145:1
4136:4
4133:3
4126:0
4121:0
4116:1
4109:[
4105:=
4102:]
4099:B
4095:|
4091:I
4088:[
4066:.
4062:]
4055:1
4050:0
4045:0
4040:2
4035:1
4027:0
4020:0
4015:1
4010:0
4005:1
3997:2
3992:1
3982:0
3977:0
3972:1
3967:0
3962:1
3954:2
3947:[
3943:=
3940:]
3937:I
3933:|
3929:A
3926:[
3904:.
3899:]
3893:2
3888:1
3880:0
3873:1
3865:2
3860:1
3850:0
3845:1
3837:2
3831:[
3826:=
3823:A
3809:A
3803:I
3797:A
3791:I
3785:A
3779:n
3775:n
3766:n
3762:n
3756:A
3747:n
3743:n
3733:n
3729:n
3723:A
3703:n
3692:n
3668:)
3665:!
3662:n
3658:n
3655:(
3640:)
3638:n
3630:n
3626:n
3609:.
3604:d
3600:)
3597:B
3594:(
3579:=
3576:)
3573:A
3570:(
3557:B
3553:d
3549:A
3545:d
3541:B
3537:A
3436:x
3429:y
3422:z
3416:y
3396:.
3391:3
3387:L
3374:1
3370:L
3366:+
3361:3
3357:L
3349:,
3344:2
3340:L
3327:1
3323:L
3316:2
3313:3
3307:+
3302:2
3298:L
3282:3
3279:L
3273:1
3270:L
3264:3
3261:L
3256:x
3251:2
3248:L
3242:1
3239:L
3233:2
3230:/
3227:3
3218:2
3215:L
3210:x
3188:]
3181:1
3173:1
3168:0
3163:0
3156:3
3151:0
3146:1
3141:0
3134:2
3129:0
3124:0
3119:1
3112:[
3084:1
3080:L
3067:1
3063:L
3056:2
3053:1
3041:1
3037:L
3024:2
3020:L
3011:1
3007:L
2976:1
2966:=
2957:z
2941:3
2934:=
2921:y
2909:2
2902:=
2885:x
2857:]
2850:1
2842:1
2837:0
2832:0
2825:3
2820:0
2815:1
2810:0
2803:7
2798:0
2793:1
2788:2
2781:[
2753:3
2749:L
2736:3
2732:L
2719:2
2715:L
2702:2
2698:L
2694:2
2664:1
2654:=
2645:z
2631:3
2624:=
2611:y
2601:7
2594:=
2581:y
2574:+
2565:x
2562:2
2534:]
2527:1
2522:1
2514:0
2509:0
2500:2
2497:3
2490:0
2483:2
2480:1
2473:0
2466:7
2461:0
2456:1
2451:2
2444:[
2416:2
2412:L
2399:3
2395:L
2388:2
2385:1
2379:+
2374:2
2370:L
2360:1
2356:L
2343:3
2339:L
2330:1
2326:L
2295:1
2290:=
2281:z
2256:2
2253:3
2245:=
2234:y
2228:2
2225:1
2212:7
2207:=
2196:y
2189:+
2180:x
2177:2
2144:]
2137:1
2132:1
2124:0
2119:0
2112:1
2105:2
2102:1
2093:2
2090:1
2083:0
2076:8
2071:1
2063:1
2058:2
2051:[
2027:3
2023:L
2014:2
2010:L
2006:4
2000:+
1995:3
1991:L
1964:1
1957:=
1948:z
1933:1
1926:=
1917:z
1911:2
1908:1
1898:+
1889:y
1883:2
1880:1
1867:8
1860:=
1851:z
1835:y
1828:+
1819:x
1816:2
1788:]
1781:5
1776:1
1771:2
1766:0
1759:1
1752:2
1749:1
1740:2
1737:1
1730:0
1723:8
1718:1
1710:1
1705:2
1698:[
1670:3
1666:L
1653:1
1649:L
1645:+
1640:3
1636:L
1626:2
1622:L
1609:1
1605:L
1598:2
1595:3
1589:+
1584:2
1580:L
1549:5
1542:=
1533:z
1526:+
1517:y
1514:2
1504:1
1497:=
1488:z
1482:2
1479:1
1469:+
1460:y
1454:2
1451:1
1438:8
1431:=
1422:z
1406:y
1399:+
1390:x
1387:2
1359:]
1352:3
1344:2
1339:1
1334:2
1316:2
1311:1
1303:3
1293:8
1288:1
1280:1
1275:2
1268:[
1239:3
1229:=
1220:z
1217:2
1210:+
1201:y
1194:+
1185:x
1182:2
1161:=
1152:z
1149:2
1142:+
1133:y
1117:x
1114:3
1103:8
1096:=
1087:z
1071:y
1064:+
1055:x
1052:2
1015:2
1012:L
1007:y
1002:1
999:L
994:x
970:)
965:3
961:L
957:(
949:3
939:=
930:z
927:2
920:+
911:y
904:+
895:x
892:2
882:)
877:2
873:L
869:(
851:=
842:z
839:2
832:+
823:y
807:x
804:3
794:)
789:1
785:L
781:(
773:8
766:=
757:z
741:y
734:+
725:x
722:2
683:.
678:]
672:0
667:0
662:0
657:0
650:1
642:3
634:0
629:0
622:1
614:1
606:2
598:0
592:[
542:.
459:]
453:0
448:0
443:0
438:0
431:4
426:1
421:1
416:0
409:3
401:2
393:0
388:1
382:[
372:]
366:0
361:0
356:0
351:0
344:8
336:2
328:2
320:0
313:9
308:1
303:3
298:1
292:[
282:]
276:8
271:2
266:2
261:0
254:8
246:2
238:2
230:0
223:9
218:1
213:3
208:1
202:[
192:]
181:5
171:3
164:1
159:1
151:1
146:1
139:9
134:1
129:3
124:1
118:[
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
