Gaussian elimination for a singular square matrix

In summary: I'm sorry, I made a mistake copying the matrix and consequently a mistake in row operations. The correct example should be:\left (\begin{array}{ccc}0 & 1 & 2 \\0 & -1 & 1 \\0 & 1 & 0 \\0 & 0 & 0 \end{array}\right ) \to\left (\begin{array}{ccc}0 & 1 & 2 \\0 & -1 & 1 \\0 & 0 & 0 \\0 & 0 & 0 \end{array}\right ) In this case, the resulting matrix is not in row echelon form, but it is in reduced row echelon form
  • #1
cianfa72
1,799
198
TL;DR Summary
Gauss elimination applied to a singular square matrix
Hi,

I've the following doubt: consider an homogeneous linear system ##Ax=0## with ##A## a singular square matrix.

The resulting matrix attained through Gaussian elimination will be in upper triangular or raw echelon form ?

Thanks.
 
Physics news on Phys.org
  • #2
I see no trouble with obtaining upper/lower triangular echelon form. You have linearly dependent rows, so at least one row will be zeroed out.
 
  • #3
cianfa72 said:
Summary: Gauss elimination applied to a singular square matrix

Hi,

I've the following doubt: consider an homogeneous linear system ##Ax=0## with ##A## a singular square matrix.

The resulting matrix attained through Gaussian elimination will be in upper triangular or raw echelon form ?

Thanks.
Vectors ##x## with ##Ax=0## build a subspace ##K##, the kernel of ##A##. Singular only means that ##\dim K > 0##. Say we have ##\dim K =m##, then Gauß elimination will lead to ##m## rows of zeroes.
 
  • #4
fresh_42 said:
Vectors ##x## with ##Ax=0## build a subspace ##K##, the kernel of ##A##. Singular only means that ##\dim K > 0##. Say we have ##\dim K =m##, then Gauss elimination will lead to ##m## rows of zeroes.
Sure...but my point is: a raw echelon square matrix is also upper triangular; for non-singular matrices the reverse is also true: a non-singular upper triangular square matrix is also raw echelon.

Now in case of singular square matrix ##A# , Gauss elimination will lead to just an upper triangular or even a raw echelon ?
 
Last edited:
  • #5
Is a zero matrix in row echelon form?
 
  • #6
nuuskur said:
Is a zero matrix in row echelon form?
Yes, from its definition I believe...
 
  • #7
Regularity does not play a role in whether you will be able to achieve row echelon form. Start with
[tex]
\left (\begin{array}{cccccc}
a_{11} & a_{12} & a_{13} & \ldots & a_{1n} & 0 \\
a_{21} & a_{22} & a_{23} & \ldots & a_{2n} & 0 \\
\vdots \\
a_{n1} & a_{n2} & a_{n3} & \ldots & a_{nn} & 0
\end{array}\right )
[/tex]
Re-arrange such that ## a_{11} \neq 0##. Then zero first column under ##a_{11}##. Otherwise, the first column is zero. Leave first row fixed from now on. Then re-arrange rows ##2\ldots n##, if necessary, such that ##a_{22} \neq 0## and zero the second column under ##a_{22}##. Proceed analogously with subsequent rows. The result will be of row exchelon form.
 
Last edited:
  • #8
nuuskur said:
Regularity does not play a role in whether you will be able to achieve row echelon form. Start with
[tex]
\left (\begin{array}{cccccc}
a_{11} & a_{12} & a_{13} & \ldots & a_{1n} & 0 \\
a_{21} & a_{22} & a_{23} & \ldots & a_{2n} & 0 \\
\vdots \\
a_{n1} & a_{n2} & a_{n3} & \ldots & a_{nn} & 0
\end{array}\right )
[/tex]
Re-arrange such that ## a_{11} \neq 0##. Then zero first column under ##a_{11}##. Otherwise, the first column is zero. Leave first row fixed from now on. Then re-arrange rows ##2\ldots n##, if necessary, such that ##a_{22} \neq 0## and zero the second column under ##a_{22}##. Proceed analogously. The result will be of row exchelon form.
Consider the following case: first column zero, ## a_{12} = 0##, ## a_{22} \neq 0##, ## a_{13} \neq 0##.
In this case the result would not be of raw echelon form, I believe...
 
Last edited:
  • #9
cianfa72 said:
Consider the following case: first column zero, ## a_{12} = 0##, ## a_{22} \neq 0##, ## a_{13} \neq 0##.
In this case the result would not be of raw echelon form, I believe...
Thinking about it, I believe a column skip is needed in order to get a raw echelon matrix in that case. By the way I found the following into "Elementary Linear Algebra" book

Occasionally when we progress to a new column, the pivot entry as well as all lower
entries in that column are zero. Here,a type (III) operation cannot help. In such cases,
we skip over the current column and advance to the next column to the right. Hence,
the new pivot entry is located horizontally to the right from where we would normally
expect it


Do you think it make sense ?
 
  • #10
It makes sense, but I don't see how it pertains to our discussion.
cianfa72 said:
Consider the following case: first column zero, ## a_{12} = 0##, ## a_{22} \neq 0##, ## a_{13} \neq 0##.
I considered it, I don't see any problems. ##a_{13}\neq 0## is irrelevant. Let's work through an example, maybe that'll clear something up. I'll just work with some matrix ##A## without augmenting it. Per your specifications:
[tex]
\left (\begin{array}{ccc}0 & 1 & 2 & 0 \\
0 & -1 & 1 & 1 \\
0 & 1 & 0 & 1 \\
0 & 1 & 1 & 1 \end{array}\right ) \to
\left (\begin{array}{ccc}0 & 1 & 2 & 0 \\
0 & -1 & 1 & 1 \\
0 & 0 & 1 & 2 \\
0 & 0 & 2 & 2 \end{array}\right ) \to
\left (\begin{array}{ccc}0 & 1 & 2 & 0 \\
0 & -1 & 1 & 1 \\
0 & 0 & 1 & 2 \\
0 & 0 & 0 & -2 \end{array}\right )
[/tex]
which can be further transformed to row echelon form. You can further transform it into reduced row echelon form, too.
 
  • #11
nuuskur said:
I considered it, I don't see any problems. ##a_{13}\neq 0## is irrelevant. Let's work through an example, maybe that'll clear something up. I'll just work with some matrix ##A## without augmenting it.
In your example ##a_{12}## was not zero; take instead the following matrix

[tex]
\left (\begin{array}{ccc}0 & 0 & 2 & 0 \\
0 & -1 & 1 & 1 \\
0 & 1 & 0 & 1 \\
0 & 1 & 1 & 1 \end{array}\right )
[/tex]
 
  • #12
Oh, well, regardless, it has no effect. For the record: any matrix can be transformed to reduced row echelon form.
 
  • #13
nuuskur said:
Oh, well, regardless, it has no effect.
anyway if the first column is not skipped (starting elimination at ##a_{12}##) we are not able to transform it in raw echelon form, don't you ?
 
Last edited:
  • #14
cianfa72 said:
anyway if the first column is not skipped (starting elimination at ##a_{12}##) ) we are not able to transform it in raw echelon form, don't you ?
I don't understand what you mean. Choose a column at random and a nonzero element in it, then zero the rest of the column. If the column is already zero you don't have to touch that column.
 
  • #15
nuuskur said:
I don't understand what you mean. Choose a column at random and a nonzero element in it, then zero the rest of the column. If the column is already zero you don't have to touch that column.
ok, maybe this point was not clear to me.
 

1. What is Gaussian elimination for a singular square matrix?

Gaussian elimination is a method used to solve a system of linear equations by transforming the equations into a simpler form. For a singular square matrix, the method involves reducing the matrix to row-echelon form, where all the entries below the main diagonal are zero. This allows for the identification of the solutions to the system of equations.

2. How does Gaussian elimination work for a singular square matrix?

Gaussian elimination works by using elementary row operations to transform the matrix into row-echelon form. These operations include multiplying a row by a non-zero constant, swapping two rows, and adding a multiple of one row to another row. By performing these operations, the matrix is reduced to a simpler form where the solutions can be easily identified.

3. Can Gaussian elimination be used for non-square matrices?

No, Gaussian elimination can only be used for square matrices. This is because the method relies on transforming the matrix into row-echelon form, which can only be achieved for square matrices. For non-square matrices, other methods such as Gauss-Jordan elimination can be used.

4. What are the advantages of using Gaussian elimination for a singular square matrix?

Gaussian elimination is a reliable and efficient method for solving systems of linear equations. It eliminates the need for guesswork and trial-and-error methods, and can be easily implemented using computer algorithms. Additionally, the method provides a systematic approach for finding the solutions to a system of equations.

5. Are there any limitations to using Gaussian elimination for a singular square matrix?

One limitation of Gaussian elimination for a singular square matrix is that it may not always be able to find the solutions to a system of equations. This can happen if the matrix is ill-conditioned or if there are round-off errors in the calculations. In such cases, alternative methods may need to be used to obtain accurate solutions.

Similar threads

  • Linear and Abstract Algebra
Replies
26
Views
4K
  • Linear and Abstract Algebra
Replies
6
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
853
  • Calculus and Beyond Homework Help
Replies
1
Views
628
  • Linear and Abstract Algebra
Replies
15
Views
1K
  • Linear and Abstract Algebra
Replies
13
Views
6K
  • Linear and Abstract Algebra
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
2K
  • Linear and Abstract Algebra
Replies
4
Views
3K
Back
Top