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