[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki3\/leibniz-formula-for-determinants-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki3\/leibniz-formula-for-determinants-wikipedia\/","headline":"Leibniz formula for determinants – Wikipedia","name":"Leibniz formula for determinants – Wikipedia","description":"Mathematics formula In algebra, the Leibniz formula, named in honor of Gottfried Leibniz, expresses the determinant of a square matrix","datePublished":"2015-05-10","dateModified":"2015-05-10","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki3\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki3\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/cd810e53c1408c38cc766bc14e7ce26a?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/cd810e53c1408c38cc766bc14e7ce26a?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/11\/book.png","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/11\/book.png","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/7daff47fa58cdfd29dc333def748ff5fa4c923e3","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/7daff47fa58cdfd29dc333def748ff5fa4c923e3","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki3\/leibniz-formula-for-determinants-wikipedia\/","wordCount":13539,"articleBody":"Mathematics formula  In algebra, the Leibniz formula, named in honor of Gottfried Leibniz, expresses the determinant of a square matrix in terms of permutations of the matrix elements. If A{displaystyle A} is an n\u00d7n{displaystyle ntimes n} matrix, where   aij{displaystyle a_{ij}} is the entry in the i{displaystyle i}-th row and j{displaystyle j}-th column of A{displaystyle A}, the formula is  det(A)=\u2211\u03c4\u2208Snsgn\u2061(\u03c4)\u220fi=1nai,\u03c4(i)=\u2211\u03c3\u2208Snsgn\u2061(\u03c3)\u220fi=1na\u03c3(i),i{displaystyle det(A)=sum _{tau in S_{n}}operatorname {sgn}(tau )prod _{i=1}^{n}a_{i,,tau (i)}=sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}a_{sigma (i),,i}}where sgn{displaystyle operatorname {sgn} } is the sign function of permutations in the permutation group Sn{displaystyle S_{n}}, which returns +1{displaystyle +1} and \u22121{displaystyle -1} for even and odd permutations, respectively.Another common notation used for the formula is in terms of the Levi-Civita symbol and makes use of the Einstein summation notation, where it becomesdet(A)=\u03f5i1\u22efina1i1\u22efanin,{displaystyle det(A)=epsilon _{i_{1}cdots i_{n}}{a}_{1i_{1}}cdots {a}_{ni_{n}},}which may be more familiar to physicists.Directly evaluating the Leibniz formula from the definition requires \u03a9(n!\u22c5n){displaystyle Omega (n!cdot n)}  operations in general\u2014that is, a number of operations asymptotically proportional to n{displaystyle n} factorial\u2014because n!{displaystyle n!} is the number of order-n{displaystyle n} permutations.  This is impractically difficult for even relatively small n{displaystyle n}.  Instead, the determinant can be evaluated in O(n3){displaystyle O(n^{3})} operations by forming the LU decomposition A=LU{displaystyle A=LU} (typically via Gaussian elimination or similar methods), in which case detA=detL\u22c5detU{displaystyle det A=det Lcdot det U} and the determinants of the triangular matrices L{displaystyle L} and U{displaystyle U} are simply the products of their diagonal entries.  (In practical applications of numerical linear algebra, however, explicit computation of the determinant is rarely required.)  See, for example, Trefethen & Bau (1997). The determinant can also be evaluated in fewer than O(n3){displaystyle O(n^{3})} operations by reducing the problem to matrix multiplication, but most such algorithms are not practical.Formal statement and proof[edit]Theorem.There exists exactly one function F:Mn(K)\u2192K{displaystyle F:M_{n}(mathbb {K} )rightarrow mathbb {K} } which is alternating multilinear w.r.t. columns and such that F(I)=1{displaystyle F(I)=1}.Proof.Uniqueness: Let F{displaystyle F} be such a function, and let A=(aij)i=1,\u2026,nj=1,\u2026,n{displaystyle A=(a_{i}^{j})_{i=1,dots ,n}^{j=1,dots ,n}} be an n\u00d7n{displaystyle ntimes n} matrix. Call Aj{displaystyle A^{j}} the j{displaystyle j}-th column of A{displaystyle A}, i.e. Aj=(aij)i=1,\u2026,n{displaystyle A^{j}=(a_{i}^{j})_{i=1,dots ,n}}, so that A=(A1,\u2026,An).{displaystyle A=left(A^{1},dots ,A^{n}right).}Also, let Ek{displaystyle E^{k}} denote the k{displaystyle k}-th column vector of the identity matrix.Now one writes each of the Aj{displaystyle A^{j}}‘s in terms of the Ek{displaystyle E^{k}}, i.e.Aj=\u2211k=1nakjEk{displaystyle A^{j}=sum _{k=1}^{n}a_{k}^{j}E^{k}}.As F{displaystyle F} is multilinear, one hasF(A)=F(\u2211k1=1nak11Ek1,\u2026,\u2211kn=1naknnEkn)=\u2211k1,\u2026,kn=1n(\u220fi=1nakii)F(Ek1,\u2026,Ekn).{displaystyle {begin{aligned}F(A)&=Fleft(sum _{k_{1}=1}^{n}a_{k_{1}}^{1}E^{k_{1}},dots ,sum _{k_{n}=1}^{n}a_{k_{n}}^{n}E^{k_{n}}right)=sum _{k_{1},dots ,k_{n}=1}^{n}left(prod _{i=1}^{n}a_{k_{i}}^{i}right)Fleft(E^{k_{1}},dots ,E^{k_{n}}right).end{aligned}}}From alternation it follows that any term with repeated indices is zero. The sum can therefore be restricted to tuples with non-repeating indices, i.e. permutations:F(A)=\u2211\u03c3\u2208Sn(\u220fi=1na\u03c3(i)i)F(E\u03c3(1),\u2026,E\u03c3(n)).{displaystyle F(A)=sum _{sigma in S_{n}}left(prod _{i=1}^{n}a_{sigma (i)}^{i}right)F(E^{sigma (1)},dots ,E^{sigma (n)}).}Because F is alternating, the columns E{displaystyle E} can be swapped until it becomes the identity.  The sign function sgn\u2061(\u03c3){displaystyle operatorname {sgn}(sigma )} is defined to count the number of swaps necessary and account for the resulting sign change.  One finally gets:F(A)=\u2211\u03c3\u2208Snsgn\u2061(\u03c3)(\u220fi=1na\u03c3(i)i)F(I)=\u2211\u03c3\u2208Snsgn\u2061(\u03c3)\u220fi=1na\u03c3(i)i{displaystyle {begin{aligned}F(A)&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )left(prod _{i=1}^{n}a_{sigma (i)}^{i}right)F(I)\\&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}a_{sigma (i)}^{i}end{aligned}}}as F(I){displaystyle F(I)} is required to be equal to 1{displaystyle 1}.Therefore no function besides the function defined by the Leibniz Formula can be a multilinear alternating function with F(I)=1{displaystyle Fleft(Iright)=1}.Existence: We now show that F, where F is the function defined by the Leibniz formula, has these three properties.Multilinear:F(A1,\u2026,cAj,\u2026)=\u2211\u03c3\u2208Snsgn\u2061(\u03c3)ca\u03c3(j)j\u220fi=1,i\u2260jna\u03c3(i)i=c\u2211\u03c3\u2208Snsgn\u2061(\u03c3)a\u03c3(j)j\u220fi=1,i\u2260jna\u03c3(i)i=cF(A1,\u2026,Aj,\u2026)F(A1,\u2026,b+Aj,\u2026)=\u2211\u03c3\u2208Snsgn\u2061(\u03c3)(b\u03c3(j)+a\u03c3(j)j)\u220fi=1,i\u2260jna\u03c3(i)i=\u2211\u03c3\u2208Snsgn\u2061(\u03c3)((b\u03c3(j)\u220fi=1,i\u2260jna\u03c3(i)i)+(a\u03c3(j)j\u220fi=1,i\u2260jna\u03c3(i)i))=(\u2211\u03c3\u2208Snsgn\u2061(\u03c3)b\u03c3(j)\u220fi=1,i\u2260jna\u03c3(i)i)+(\u2211\u03c3\u2208Snsgn\u2061(\u03c3)\u220fi=1na\u03c3(i)i)=F(A1,\u2026,b,\u2026)+F(A1,\u2026,Aj,\u2026){displaystyle {begin{aligned}F(A^{1},dots ,cA^{j},dots )&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )ca_{sigma (j)}^{j}prod _{i=1,ineq j}^{n}a_{sigma (i)}^{i}\\&=csum _{sigma in S_{n}}operatorname {sgn}(sigma )a_{sigma (j)}^{j}prod _{i=1,ineq j}^{n}a_{sigma (i)}^{i}\\&=cF(A^{1},dots ,A^{j},dots )\\\\F(A^{1},dots ,b+A^{j},dots )&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )left(b_{sigma (j)}+a_{sigma (j)}^{j}right)prod _{i=1,ineq j}^{n}a_{sigma (i)}^{i}\\&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )left(left(b_{sigma (j)}prod _{i=1,ineq j}^{n}a_{sigma (i)}^{i}right)+left(a_{sigma (j)}^{j}prod _{i=1,ineq j}^{n}a_{sigma (i)}^{i}right)right)\\&=left(sum _{sigma in S_{n}}operatorname {sgn}(sigma )b_{sigma (j)}prod _{i=1,ineq j}^{n}a_{sigma (i)}^{i}right)+left(sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}a_{sigma (i)}^{i}right)\\&=F(A^{1},dots ,b,dots )+F(A^{1},dots ,A^{j},dots )\\\\end{aligned}}}Alternating:F(\u2026,Aj1,\u2026,Aj2,\u2026)=\u2211\u03c3\u2208Snsgn\u2061(\u03c3)(\u220fi=1,i\u2260j1,i\u2260j2na\u03c3(i)i)a\u03c3(j1)j1a\u03c3(j2)j2{displaystyle {begin{aligned}F(dots ,A^{j_{1}},dots ,A^{j_{2}},dots )&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )left(prod _{i=1,ineq j_{1},ineq j_{2}}^{n}a_{sigma (i)}^{i}right)a_{sigma (j_{1})}^{j_{1}}a_{sigma (j_{2})}^{j_{2}}\\end{aligned}}}For any \u03c3\u2208Sn{displaystyle sigma in S_{n}} let \u03c3\u2032{displaystyle sigma ‘} be the tuple equal to \u03c3{displaystyle sigma } with the j1{displaystyle j_{1}} and j2{displaystyle j_{2}} indices switched.F(A)=\u2211\u03c3\u2208Sn,\u03c3(j1)(\u03c3)(\u220fi=1,i\u2260j1,i\u2260j2na\u03c3(i)i)a\u03c3(j1)j1a\u03c3(j2)j2+sgn\u2061(\u03c3\u2032)(\u220fi=1,i\u2260j1,i\u2260j2na\u03c3\u2032(i)i)a\u03c3\u2032(j1)j1a\u03c3\u2032(j2)j2]=\u2211\u03c3\u2208Sn,\u03c3(j1)(\u03c3)(\u220fi=1,i\u2260j1,i\u2260j2na\u03c3(i)i)a\u03c3(j1)j1a\u03c3(j2)j2\u2212sgn\u2061(\u03c3)(\u220fi=1,i\u2260j1,i\u2260j2na\u03c3(i)i)a\u03c3(j2)j1a\u03c3(j1)j2]=\u2211\u03c3\u2208Sn,\u03c3(j1)(\u03c3)(\u220fi=1,i\u2260j1,i\u2260j2na\u03c3(i)i)(a\u03c3(j1)j1a\u03c3(j2)j2\u2212a\u03c3(j1)j2a\u03c3(j2)j1)\u23df=0, if\u00a0Aj1=Aj2{displaystyle {begin{aligned}F(A)&=sum _{sigma in S_{n},sigma (j_{1}),Aj2,\u2026)=0{displaystyle F(dots ,A^{j_{1}},dots ,A^{j_{2}},dots )=0}.Finally, F(I)=1{displaystyle F(I)=1}:F(I)=\u2211\u03c3\u2208Snsgn\u2061(\u03c3)\u220fi=1nI\u03c3(i)i=\u2211\u03c3\u2208Snsgn\u2061(\u03c3)\u220fi=1n\u03b4i,\u03c3(i)=\u2211\u03c3\u2208Snsgn\u2061(\u03c3)\u03b4\u03c3,id{1\u2026n}=sgn\u2061(id{1\u2026n})=1{displaystyle {begin{aligned}F(I)&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}I_{sigma (i)}^{i}=sum _{sigma in S_{n}}operatorname {sgn}(sigma )prod _{i=1}^{n}operatorname {delta } _{i,sigma (i)}\\&=sum _{sigma in S_{n}}operatorname {sgn}(sigma )operatorname {delta } _{sigma ,operatorname {id} _{{1ldots n}}}=operatorname {sgn}(operatorname {id} _{{1ldots n}})=1end{aligned}}}Thus the only alternating multilinear functions with F(I)=1{displaystyle F(I)=1} are restricted to the function defined by the Leibniz formula, and it in fact also has these three properties. Hence the determinant can be defined as the only function det:Mn(K)\u2192K{displaystyle det :M_{n}(mathbb {K} )rightarrow mathbb {K} } with these three properties.See also[edit]References[edit]"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki3\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki3\/leibniz-formula-for-determinants-wikipedia\/#breadcrumbitem","name":"Leibniz formula for determinants – Wikipedia"}}]}]