Maths - Matrix algebra - Determinants - sci.math

Message 1 in thread
From: Boruch
Subject: Determinant Calculating
Newsgroups: sci.math
Date: 2003-02-24 16:07:01 PST

Hello I'm looking for a fast way of computing the determinant of large
matrices, can anybody help?

---

Message 2 in thread
From: Dann Corbit
Subject: Re: Determinant Calculating
Newsgroups: sci.math
Date: 2003-02-24 17:05:15 PST

"Boruch" wrote in message
news:3ca1703f.0302241607.37431d4d@posting.google.com...
> Hello I'm looking for a fast way of computing the determinant of large
> matrices, can anybody help?

Do a Gaussian elimination and then take the product of the diagonal
elements.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm

---

Message 3 in thread
From: Robert Israel
Subject: Re: Determinant Calculating
Newsgroups: sci.math
Date: 2003-02-24 17:05:17 PST

In article <3ca1703f.0302241607.37431d4d@posting.google.com>,
Boruch wrote:
>Hello I'm looking for a fast way of computing the determinant of large
>matrices, can anybody help?

How large? Sparse or dense? Integer or real entries? In what language
or computer algebra system?

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2

---

Message 4 in thread
From: Boruch (bkold2day@hotmail.com)
Subject: Re: Determinant Calculating
Newsgroups: sci.math
Date: 2003-02-26 16:05:21 PST

> How large? it varies from small to huge
> Sparse or dense? what is that??
> Integer or real entries? all integers

---

Message 5 in thread From: Robert Israel

Subject: Re: Determinant Calculating View this article only Newsgroups: sci.mathDate: 2003-02-26 18:39:52 PST In article <3ca1703f.0302261605.4d4b0f3b@posting.google.com>,
Boruch <bkold2day@hotmail.com> wrote:
>> How large?
>it varies from small to huge

One person's huge might be another's small.

>> Sparse or dense?
>what is that??

Sparse matrices have most entries 0. This can have important
implications for efficient storage and various linear-algebra
manipulations of the matrix.

>> Integer or real entries?
>all integers

OK, that's important. And you want the result as an
integer? Well, you could use a fraction-free Gaussian
elimination method for this case.
On the other hand, if you know the determinant is not too big
you might save a lot of time by using a modular method for
several primes and the Chinese Remainder Theorem to reconstruct
the answer.

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2

---

Message 6 in thread From: Jeffrey H

Subject: Re: Determinant Calculating View this article only Newsgroups: sci.mathDate: 2003-02-27 06:54:14 PST

I have a related question that may or may not have an obvious answer,
but I just can't see it. If you have a 4x4 matrix, is the determinant
the same as if you take the determinants of the 2x2 matrices formed by
splitting the first matrix into four parts, and then taking the
determinant of the 2x2 matrix formed by these 4 determinants?

israel@math.ubc.ca (Robert Israel) wrote:

>In article <3ca1703f.0302261605.4d4b0f3b@posting.google.com>,
>Boruch <bkold2day@hotmail.com> wrote:
>>> How large?
>>it varies from small to huge
>
>One person's huge might be another's small.
>
>>> Sparse or dense?
>>what is that??
>
>Sparse matrices have most entries 0. This can have important
>implications for efficient storage and various linear-algebra
>manipulations of the matrix.
>
>>> Integer or real entries?
>>all integers
>
>OK, that's important. And you want the result as an
>integer? Well, you could use a fraction-free Gaussian
>elimination method for this case.
>On the other hand, if you know the determinant is not too big
>you might save a lot of time by using a modular method for
>several primes and the Chinese Remainder Theorem to reconstruct
>the answer.
>
>Robert Israel israel@math.ubc.ca
>Department of Mathematics http://www.math.ubc.ca/~israel
>University of British Columbia
>Vancouver, BC, Canada V6T 1Z2 Post a follow-up to this message

---

Message 7 in thread From: Robin Chapman

Subject: Re: Determinant Calculating

Newsgroups: sci.mathDate: 2003-02-27 07:09:14 PST Jeffrey H wrote:

>
> I have a related question that may or may not have an obvious answer,
> but I just can't see it. If you have a 4x4 matrix, is the determinant
> the same as if you take the determinants of the 2x2 matrices formed by
> splitting the first matrix into four parts, and then taking the
> determinant of the 2x2 matrix formed by these 4 determinants?

The answer is obvious once you try this with a "randomly" chosen 4 by 4
matrix :-)

--
Robin Chapman, www.maths.ex.ac.uk/~rjc/rjc.html
"His mind has been corrupted by colours, sounds and shapes."
The League of Gentlemen

---

Message 8 in thread

From: Zdislav V. Kovarik

Subject: Re: Determinant Calculating

Newsgroups: sci.mathDate: 2003-02-27 07:20:05 PST On Thu, 27 Feb 2003, Jeffrey H wrote:

>
> I have a related question that may or may not have an obvious answer,
> but I just can't see it. If you have a 4x4 matrix, is the determinant
> the same as if you take the determinants of the 2x2 matrices formed by
> splitting the first matrix into four parts, and then taking the
> determinant of the 2x2 matrix formed by these 4 determinants?
>

For goodness' sake, experiment before asking curious questions
like this.

On my computer, the first randomly generated integer matrix
provided a counterexample:

A =
[ 0 -1 0 -1
-2 1 0 2
0 1 0 0
0 0 1 0 ]

det(A)=-2 but your suggestion gives 0.

To hammer it in, since the difference between these
expressions is a polynomial which is non-zero once,
the set of counterexamples is open and dense in R^16
with complement of Lebesgue measure zero.
(The set of examples to the affirmative is negligible.)

Cheers, ZVK(Slavek).

---

Message 9 in thread From: Robert B. Israel (israel@math.ubc.ca)

Subject: Re: Determinant Calculating

Newsgroups: sci.math

Date: 2003-02-27 19:10:06 PST Jeffrey H wrote in message news:<3e5e27dd.3786585@news.mindspring.com>...
> I have a related question that may or may not have an obvious answer,
> but I just can't see it. If you have a 4x4 matrix, is the determinant
> the same as if you take the determinants of the 2x2 matrices formed by
> splitting the first matrix into four parts, and then taking the
> determinant of the 2x2 matrix formed by these 4 determinants?

As others have mentioned, the answer is no. Perhaps, though, you're
thinking of something like this: if you write a square matrix in blocks as
[ A B ]
M = [ C D ] and A is invertible, then
det(M) = det(A) det(D - A C A^(-1) B).
Here M is (n+m) by (n+m), A is n by n and D is m by m.
In particular, if A and C commute (which of course requires n=m) then
det(M) = det(A D - C B) (without the requirement that A be invertible).
See e.g. the sci.math thread "determinant of block matrix" from
September 2002.

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2