Author 
Message 
Mark science forum addict
Joined: 02 May 2005
Posts: 51

Posted: Thu Jul 20, 2006 11:41 pm Post subject:
wonderful!



I've never thought of the determinant in terms of the determinant of
blocks of submatrices! 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

Posted: Thu Jul 20, 2006 11:20 am Post subject:
Re: sign of the determinant of an augmented matrix?



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

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



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

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



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

Posted: Thu Jul 20, 2006 1:30 am Post subject:
sign of the determinant of an augmented matrix?



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 



The time now is Wed Oct 17, 2018 3:34 am  All times are GMT

