0

Please note that here is Gauss_jordan elimination which help us get inverse of A.

I am wondering, is there any condition that it could work without pivoting?

I try to prove this under column diagonally dominant, but I could pass one step in my proof.

Has anyone heard about sth about this topic?

yes, we could naively say for each step $A^{(i)}$ has no 0 elements in the diagonal line but could we directly add some conditions on A rather than $A^{(i)}$?

thanks

airbender
  • 13
  • This can only be done when you don't have zeros in the diagonal. – Luis Costa Oct 12 '14 at 23:27
  • yes, but the condition is based on $A^{(i)}$ of each step not on A itself. What do you think? – airbender Oct 12 '14 at 23:30
  • Yes, that is what I meant. But be careful because without pivoting GJ is numerically unstable. – Luis Costa Oct 12 '14 at 23:33
  • But I feel it is not a condition directly on A, how could we tell others that in each step, there is no 0. Like LU factorization, if the A is diagonally dominant, then no pivoting needed. Is there something like this? – airbender Oct 12 '14 at 23:34
  • The stability of the algorithm is determined by the chosen norm and the residual in each step. Look at its LU decomposition. If $| L |{\infty}| U |{\infty}$ is a small multiple of $| A |{\infty}$, then we can say that $| \delta A |{\infty}/ | A |_{\infty}$ is a small multiple of roundoff error and you have stability. – Luis Costa Oct 12 '14 at 23:55
  • no, I do not refer to stability, I mean the condition for gauss_jordan does not need pivoting – airbender Oct 12 '14 at 23:56
  • You would have to a priori calculate the determinant of the sub-matrices. This is, of course, pointless outside of an academic exercise. The sub-matrices are a feature of $A$. I think you're getting hung up on the fact that you can't just look at $A$ and decide if it will work. – Luis Costa Oct 13 '14 at 00:04
  • Thanks, but could you say more about how to connect determinant with sub matrix to the non-zero diagonal element in each step? – airbender Oct 13 '14 at 00:30
  • To verify if the sub-matrices are singular. The algorithm stops if you're not allowed to pivot. – Luis Costa Oct 13 '14 at 00:44

1 Answers1

0

I think you are asking whether a given matrix $A$ can be written as $A =L\cdot U$ where $L$ is lower triangular, $U$ is upper triangular and both are invertible. This is called the Gauss decomposition ( you may have an extra diagonal term in the middle - harmless).

The following result is true:

The matrix $A$ can be written as $A = L\cdot D \cdot U$ (all invertible) if and only if all the leading principal minors of $A$ are nonzero.

orangeskid
  • 53,909