Search   Memberlist   Usergroups
 Page 1 of 1 [5 Posts]
Author Message
Mark

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!
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
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?

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
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 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
Mark

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 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!

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [5 Posts]
 The time now is Sun Apr 21, 2019 12:25 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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