FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
sign of the determinant of an augmented matrix?
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
Author Message
Mark
science forum addict


Joined: 02 May 2005
Posts: 51

PostPosted: Thu Jul 20, 2006 11:41 pm    Post subject: wonderful! Reply with quote

I've never thought of the determinant in terms of the determinant of
blocks of sub-matrices! I think this is a workable suggestion, since
the original nxn matrix (A) was actually reduced via Gaussian
elimination (that's how the sign of its determinant was found). Better
still, the vector A^-1 B was also computed, so the additional work will
be very little.

Thanks!
Back to top
Chip Eastham
science forum Guru


Joined: 01 May 2005
Posts: 412

PostPosted: Thu Jul 20, 2006 11:20 am    Post subject: Re: sign of the determinant of an augmented matrix? Reply with quote

Robert Israel wrote:
Quote:
In article <1153364639.433798.110990@p79g2000cwp.googlegroups.com>,
Chip Eastham <hardmath@gmail.com> wrote:

Mark wrote:
Suppose I know the sign of the determinant of a large n x n banded
matrix.

Now if I append m rows and m columns to it, which are dense, making it
an 'arrow matrix' of (n + m) by (n + m). Typically m << n.

Is there an elegant way to determine the sign of this augmented matrix?
Any lead will be most appreciated.

I don't think there is generally an "elegant" way to do this.

My suggestion would be to call the new bigger matrix a
"bordered" matrix rather than "augmented". Augmented
matrix is generally used to describe adding a column or
columns for the sake of solving a linear system (perhaps
with multiple right hand sides) by Gauss elimination.

Now back to your question. Consider the block matrix:

A B
C D

where A is original (nxn) portion and the others denote
the additional m rows and columns.

The determinant of this is det(A) * det(D - C A^-1 B).

Now you probably don't have A^-1 explicitly, but if it is
banded as you state, then A^-1 B can perhaps be
found efficiently by solving (by Gauss elimination,
more or less):

A X = B

X = A^-1 B

rather than by computing A^-1 and multiplying.

Yes, and the sign of det(A) can be computed easily at the same time
as you are doing the Gauss elimination: you just need to count the
number of times you swap two rows or get a negative leading entry.
So you didn't really need to know the sign of det(A) beforehand.

It is then left to compute the determinant of (mxm)
matrix D - C A^-1 B, which is much less work than
computing the determinant of a whole (n+m)x(n+m)
matrix, right?

Hmm: D - C A^(-1) B is exactly the matrix you would have in the
lower right after doing the first n columns' worth of Gaussian
elimination on the (n+m) x (n+m) matrix. So I don't see how
it can be "less work".

Sure, overall it is exactly Gauss elimination on the whole
matrix. At top I written that generally there's no elegant
way to do it. What I mean at the end is: after taking
advantage of A banded during the elimination of the first
n rows, ie. computing A^(-1) B, we wind up with the mxm
unstructured leftovers D - C A^(-1) B.

The OP said "Typically m << n", and to that extent we're
"close" to done at that point.

The OP's knowing det(A) in advance puts me in mind of
update methods. More than det(A), we would want to
keep a factored form of A hanging around to handle any
changing "borders" B/C/D that occur.

regards, chip
Back to top
Robert B. Israel
science forum Guru


Joined: 24 Mar 2005
Posts: 2151

PostPosted: Thu Jul 20, 2006 5:53 am    Post subject: Re: sign of the determinant of an augmented matrix? Reply with quote

In article <1153364639.433798.110990@p79g2000cwp.googlegroups.com>,
Chip Eastham <hardmath@gmail.com> wrote:
Quote:

Mark wrote:
Suppose I know the sign of the determinant of a large n x n banded
matrix.

Now if I append m rows and m columns to it, which are dense, making it
an 'arrow matrix' of (n + m) by (n + m). Typically m << n.

Is there an elegant way to determine the sign of this augmented matrix?
Any lead will be most appreciated.

I don't think there is generally an "elegant" way to do this.

My suggestion would be to call the new bigger matrix a
"bordered" matrix rather than "augmented". Augmented
matrix is generally used to describe adding a column or
columns for the sake of solving a linear system (perhaps
with multiple right hand sides) by Gauss elimination.

Now back to your question. Consider the block matrix:

A B
C D

where A is original (nxn) portion and the others denote
the additional m rows and columns.

The determinant of this is det(A) * det(D - C A^-1 B).

Now you probably don't have A^-1 explicitly, but if it is
banded as you state, then A^-1 B can perhaps be
found efficiently by solving (by Gauss elimination,
more or less):

A X = B

X = A^-1 B

rather than by computing A^-1 and multiplying.

Yes, and the sign of det(A) can be computed easily at the same time
as you are doing the Gauss elimination: you just need to count the
number of times you swap two rows or get a negative leading entry.
So you didn't really need to know the sign of det(A) beforehand.

Quote:
It is then left to compute the determinant of (mxm)
matrix D - C A^-1 B, which is much less work than
computing the determinant of a whole (n+m)x(n+m)
matrix, right?

Hmm: D - C A^(-1) B is exactly the matrix you would have in the
lower right after doing the first n columns' worth of Gaussian
elimination on the (n+m) x (n+m) matrix. So I don't see how
it can be "less work".

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
Back to top
Chip Eastham
science forum Guru


Joined: 01 May 2005
Posts: 412

PostPosted: Thu Jul 20, 2006 3:03 am    Post subject: Re: sign of the determinant of an augmented matrix? Reply with quote

Mark wrote:
Quote:
Suppose I know the sign of the determinant of a large n x n banded
matrix.

Now if I append m rows and m columns to it, which are dense, making it
an 'arrow matrix' of (n + m) by (n + m). Typically m << n.

Is there an elegant way to determine the sign of this augmented matrix?
Any lead will be most appreciated.

I don't think there is generally an "elegant" way to do this.

My suggestion would be to call the new bigger matrix a
"bordered" matrix rather than "augmented". Augmented
matrix is generally used to describe adding a column or
columns for the sake of solving a linear system (perhaps
with multiple right hand sides) by Gauss elimination.

Now back to your question. Consider the block matrix:

A B
C D

where A is original (nxn) portion and the others denote
the additional m rows and columns.

The determinant of this is det(A) * det(D - C A^-1 B).

Now you probably don't have A^-1 explicitly, but if it is
banded as you state, then A^-1 B can perhaps be
found efficiently by solving (by Gauss elimination,
more or less):

A X = B

X = A^-1 B

rather than by computing A^-1 and multiplying.

It is then left to compute the determinant of (mxm)
matrix D - C A^-1 B, which is much less work than
computing the determinant of a whole (n+m)x(n+m)
matrix, right?

regards, chip
Back to top
Mark
science forum addict


Joined: 02 May 2005
Posts: 51

PostPosted: Thu Jul 20, 2006 1:30 am    Post subject: sign of the determinant of an augmented matrix? Reply with quote

Suppose I know the sign of the determinant of a large n x n banded
matrix.

Now if I append m rows and m columns to it, which are dense, making it
an 'arrow matrix' of (n + m) by (n + m). Typically m << n.

Is there an elegant way to determine the sign of this augmented matrix?
Any lead will be most appreciated.

Thanks!
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
The time now is Sat Aug 18, 2018 7:16 am | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Diagonalizable matrix aline Math 0 Wed Nov 29, 2006 3:08 am
No new posts Linear operator and determinant aline Math 0 Wed Nov 29, 2006 2:37 am
No new posts spectrum of a symmetric tridiagonal random matrix pf.buonsante@gmail.com Math 0 Wed Jul 19, 2006 9:45 am
No new posts distance matrix consolidation bird Math 6 Sat Jul 15, 2006 9:05 pm
No new posts Rank of a matrix with bounded elements eugene Math 3 Sat Jul 15, 2006 7:46 am

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0153s ][ Queries: 20 (0.0027s) ][ GZIP on - Debug on ]