Gaussian elimination for a singular square matrix

[cianfa72]

TL;DR

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.

 

[nuuskur]

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.

 

[fresh_42]

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.

 

[cianfa72]

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 ?

 

[nuuskur]

Is a zero matrix in row echelon form?

 

[cianfa72]

Is a zero matrix in row echelon form?

Yes, from its definition I believe...

 

[nuuskur]

Regularity does not play a role in whether you will be able to achieve row echelon form. Start with
<br /> \left (\begin{array}{cccccc}<br /> a_{11} &amp; a_{12} &amp; a_{13} &amp; \ldots &amp; a_{1n} &amp; 0 \\<br /> a_{21} &amp; a_{22} &amp; a_{23} &amp; \ldots &amp; a_{2n} &amp; 0 \\<br /> \vdots \\<br /> a_{n1} &amp; a_{n2} &amp; a_{n3} &amp; \ldots &amp; a_{nn} &amp; 0<br /> \end{array}\right )<br />
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.

 

[cianfa72]

Regularity does not play a role in whether you will be able to achieve row echelon form. Start with
<br /> \left (\begin{array}{cccccc}<br /> a_{11} &amp; a_{12} &amp; a_{13} &amp; \ldots &amp; a_{1n} &amp; 0 \\<br /> a_{21} &amp; a_{22} &amp; a_{23} &amp; \ldots &amp; a_{2n} &amp; 0 \\<br /> \vdots \\<br /> a_{n1} &amp; a_{n2} &amp; a_{n3} &amp; \ldots &amp; a_{nn} &amp; 0<br /> \end{array}\right )<br />
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...

 

[cianfa72]

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 ?

 

[nuuskur]

It makes sense, but I don't see how it pertains to our discussion.

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:
<br /> \left (\begin{array}{ccc}0 &amp; 1 &amp; 2 &amp; 0 \\<br /> 0 &amp; -1 &amp; 1 &amp; 1 \\<br /> 0 &amp; 1 &amp; 0 &amp; 1 \\<br /> 0 &amp; 1 &amp; 1 &amp; 1 \end{array}\right ) \to<br /> \left (\begin{array}{ccc}0 &amp; 1 &amp; 2 &amp; 0 \\<br /> 0 &amp; -1 &amp; 1 &amp; 1 \\<br /> 0 &amp; 0 &amp; 1 &amp; 2 \\<br /> 0 &amp; 0 &amp; 2 &amp; 2 \end{array}\right ) \to<br /> \left (\begin{array}{ccc}0 &amp; 1 &amp; 2 &amp; 0 \\<br /> 0 &amp; -1 &amp; 1 &amp; 1 \\<br /> 0 &amp; 0 &amp; 1 &amp; 2 \\<br /> 0 &amp; 0 &amp; 0 &amp; -2 \end{array}\right )<br />
which can be further transformed to row echelon form. You can further transform it into reduced row echelon form, too.

 

[cianfa72]

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

<br /> \left (\begin{array}{ccc}0 &amp; 0 &amp; 2 &amp; 0 \\<br /> 0 &amp; -1 &amp; 1 &amp; 1 \\<br /> 0 &amp; 1 &amp; 0 &amp; 1 \\<br /> 0 &amp; 1 &amp; 1 &amp; 1 \end{array}\right )<br />

 

[nuuskur]

Oh, well, regardless, it has no effect. For the record: any matrix can be transformed to reduced row echelon form.

 

[cianfa72]

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 ?

 

[nuuskur]

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.

 

[cianfa72]

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.