The determinant of a matrix is a polynomial in its elements. For an antisymmetric matrix of odd order, the determinant is zero, while for an antisymmetric matrix of even order, this polynomial factors into the square of another polynomial, called the Pfaffian. Does anyone know of a simple, easy to follow, proof that the determinant factors as asserted? Gene
It's not strictly relevant, but I didn't know about it, and maybe nor did other people: an algorithm for evaluating determinants and Pfaffians without division in O(n^4) operations, which claims to outperform elimination for quite small order n for matrices with rational polynomial entries. [There is included the proof requested: short maybe, but elementary it ain't.] The URL is http://page.mi.fu-berlin.de/rote/Papers/abstract/Division-free+algorithms+fo... WFL On 10/23/08, Eugene Salamin <gene_salamin@yahoo.com> wrote:
The determinant of a matrix is a polynomial in its elements. For an antisymmetric matrix of odd order, the determinant is zero, while for an antisymmetric matrix of even order, this polynomial factors into the square of another polynomial, called the Pfaffian. Does anyone know of a simple, easy to follow, proof that the determinant factors as asserted?
Gene
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The no-division evaluation of determinants has been brought down to some exponent between 3 & 4, perhaps O(N^3.3). Pfaffians would follow, by doing the determinant, plus one square-root operation, if there's a cheap way to compute the sign for the Pfaffian. Rich ________________________________________ From: math-fun-bounces@mailman.xmission.com [math-fun-bounces@mailman.xmission.com] On Behalf Of Fred lunnon [fred.lunnon@gmail.com] Sent: Thursday, October 23, 2008 4:05 PM To: math-fun Subject: Re: [math-fun] Pfaffians It's not strictly relevant, but I didn't know about it, and maybe nor did other people: an algorithm for evaluating determinants and Pfaffians without division in O(n^4) operations, which claims to outperform elimination for quite small order n for matrices with rational polynomial entries. [There is included the proof requested: short maybe, but elementary it ain't.] The URL is http://page.mi.fu-berlin.de/rote/Papers/abstract/Division-free+algorithms+fo... WFL On 10/23/08, Eugene Salamin <gene_salamin@yahoo.com> wrote:
The determinant of a matrix is a polynomial in its elements. For an antisymmetric matrix of odd order, the determinant is zero, while for an antisymmetric matrix of even order, this polynomial factors into the square of another polynomial, called the Pfaffian. Does anyone know of a simple, easy to follow, proof that the determinant factors as asserted?
Gene
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 10/23/08, Schroeppel, Richard <rschroe@sandia.gov> wrote:
The no-division evaluation of determinants has been brought down to some exponent between 3 & 4, perhaps O(N^3.3). Pfaffians would follow, by doing the determinant, plus one square-root operation, if there's a cheap way to compute the sign for the Pfaffian.
Rich
... and if there's a cheap way to compute the square root! WFL
On 10/23/08, Schroeppel, Richard <rschroe@sandia.gov> wrote:
The no-division evaluation of determinants has been brought down to some exponent between 3 & 4, perhaps O(N^3.3). Pfaffians would follow, by doing the determinant, plus one square-root operation, if there's a cheap way to compute the sign for the Pfaffian.
Rich
... and if there's a cheap way to compute the square root! WFL
For polynomials, just gcd(f,f'). rwg
participants (4)
-
Eugene Salamin -
Fred lunnon -
rwg＠sdf.lonestar.org -
Schroeppel, Richard