Optimizing Null Space Solutions: How to Remove Zeros in Rank Deficient Matrices

[mido hoss]

Homework Statement

(Non trivial) Null space calculation with no zeros

Relevant Equations

Rref null space calculation

During calculating null space from rref matrix some rows are with 1 variable so it give this variable value of zero so the null space of rank deficient matrix be for example {-1,2,0,3,-4,0} my question is how to get rid of zeros in the null space solution and only solve it as basic and free variables so the null space contain any values except zeros for any of its variables thanks for your help in advance!

 

[fresh_42]

Can you tell us what you exactly have? What is the original matrix, how do you describe your nullspace and what have you done so far?

 

[mido hoss]

The original matrix is very large sparse matrix 3.5million * 650k with nnz elements 15million elements what i have done i have already calculated the row echelon form for this sparse matrix but in ref there are some rows with only one variable so when trying to solve this homogeneous system to get the null space the variable in single variable rows are forced to be zero neither pivot nor free to be set all i need is to make the null space zero elements take any values !

 

[fresh_42]

Oops, this does not look like homework anymore! You should have told us at the beginning. That would have saved a lot of typing.

The null space of a matrix $A$ is defined as $\operatorname{ker} A=\{\vec{x}\,|\,Ax=0\}.$
So what do you mean by variable, the vector $\vec{x}=(x_1,x_2,\ldots,x_n)$ or only one of its components $x_i,$ and what does this set $\{-1,2,0,3,-4,0\}$ mean? Is it a vector, or is it a setting of some variables $x_i$?

We don't have in front of us what you have. Does it look like ...
$$
\begin{pmatrix}a_{11}&a_{12}&a_{13}&\ldots \\
\vdots &\vdots &\vdots&\vdots \\
a_{k1}&a_{k2}&0&\ldots \\
\vdots &\vdots &\vdots&\vdots \\
a_{p1}&0&0&\ldots \\
a_{p+1\,1}&0&0&\ldots \\
a_{p+2\,1}&0&0&\ldots \\
0&0&0&\ldots \\
\vdots &\vdots &\vdots&\vdots \\
\end{pmatrix}
$$

 

[mido hoss]

sorry for inconvenience but i am new , the set i have sent is the setting of the variables yes , if you mean what my ref matrix looklike so it doesnt look like you have sent it is just normal ref but with some rows with only one variables (column)

 

[fresh_42]

We need to find a common language and I do not mean English. That's why I introduced some terms, the matrix $A,$ its kernel or null space and a vector $\vec{x}.$

If you have row with only one entry, say the $p$th row is it and $a_{pq}=0$ except $a_{pr}\neq 0$ then $A\cdot \vec{x}=\vec{0}$ yields $\vec{a}_p\cdot \vec{x}=a_{pr}x_r=0$ and therefore $x_r=0.$

So all rows with only one entry can eliminate a variable $x_r.$ This reduces the variety of vectors in the null space because we have $x_r=0$ for all vectors in $\operatorname{ker}A$.

Was that what you wanted to know?

 

[mido hoss]

Exactly thats what i mean so as you said the pth row with one entry eliminate this variable and this reducing variety of the vectors in null space all i need is to be able to introduce a value for this eliminated variable in the pth row for example so it can be free variable and share the vectors in null space so no reduction in variety of vectors in null space could this be done without affecting the original matrix properties? And sorry for the uncommon language just working on it hope you get me !

 

[fresh_42]

Exactly thats what i mean so as you said the pth row with one entry eliminate this variable and this reducing variety of the vectors in null space all i need is to be able to introduce a value for this eliminated variable in the pth row for example so it can be free variable and share the vectors in null space so no reduction in variety of vectors in null space could this be done without affecting the original matrix properties?

You want to solve $A\cdot \vec{x}=\vec{0}.$ That means for row number $p$ that we have
$$\sum_{k=1}^n a_{pk}\cdot x_k = a_{pr}\cdot x_r =0$$ if only the $r$th column has an entry different from zero, i.e. if $a_{pr}\neq 0$ and $a_{pk}=0$ for all $k\neq r.$

This means that all $\vec{x}\in \operatorname{ker}A,$ that is all vectors $\vec{x}$ for which $A\cdot \vec{x}=\vec{0}$ holds must have a zero at position $r.$ Now you can do that with all rows that have only one entry different from zero. You get another component (or the same if it is in the same column) that has to be zero for every such row. This doesn't say anything about all other components of $\vec{x}.$ They can be anything, from zero to arbitrary. That depends on the rows that are left, i.e. all the other rows.

Row manipulations don't change the result because every row is an equation. However, manipulating the columns means changing the coordinate system, i.e. the variables. So if you perform column operations, then you should do the same with the columns (no typo!) in $(x_1,x_2,x_3,\ldots,x_n).$ E.g. if you exchange column one with column two, then you rename $x_1$ by $x_2$ and $x_2$ by $x_1$. That would mix up the order of $\vec{x}$ in the end. In my example it would be $(x_2,x_1,x_3,\ldots,x_n).$ Avoid column operations, it is confusing, even if you keep track of your variables. If I remember correctly, then our professors told us to write an identity matrix $I$ next to $A$ and do everything you do with $A$ also with $I.$

 

[mido hoss]

Sorry I didn’t get you did you that neither row nor column operation or any method would fullfil my need ?

 

[fresh_42]

Sorry I didn’t get you did you that neither row nor column operation or any method would fullfil my need ?

Rows are ok, because it changes only the equations, columns are not ok because it changes variables. (You can do columns but you have to be careful.)

Here is an example:

\begin{align*}
\begin{pmatrix}-1&2&0&3&-4&0\\
-3&6&0&9&-12&0\\
3&0&0&0&0&0\\
0&0&0&-15&0&0\\
2&-4&0&-6&1&0\\
\end{pmatrix}&\cdot \begin{pmatrix}x_1\\x_2\\x_3\\x_4\\x_5\\x_6\end{pmatrix}=\begin{pmatrix}0\\0\\0\\0\\0\\0\end{pmatrix}
\\[6pt]
\begin{pmatrix}
\text{ row 2 new } &= \text{ row 2 old }-3\cdot\text{row 1}\\
\text{ row 5 new } &= \text{ row 5 old }+2\cdot\text{row 1}\\
\end{pmatrix}&\\[6pt]
\begin{pmatrix}-1&2&0&3&-4&0\\
0&0&0&0&0&0\\
0&0&0&137&0&0\\
0&0&0&-15&0&0\\
0&0&0&0&-7&0\\
\end{pmatrix}&\cdot \begin{pmatrix}x_1\\x_2\\x_3\\x_4\\x_5\\x_6\end{pmatrix}=\begin{pmatrix}0\\0\\0\\0\\0\\0\end{pmatrix}
\\[6pt]
\begin{pmatrix}
-x_1+2x_2+3x_4-4x_5&=&0\\
0&=&0\\
137x_4&=&0\\
-15x_4&=&0\\
-7x_5&=&0
\end{pmatrix}&\\[6pt]
\begin{pmatrix}
-x_1+2x_2&=&0\\
x_4&=&0\\
x_4&=&0\\
x_5&=&0
\end{pmatrix}&\\[6pt]
\end{align*}

Thus, the null space is spanned by all vectors of the form $(2x_2,x_2,x_3,0,0,x_6)$ where $x_2,x_3$ and $x_6$ are arbitrary. $x_1$ is determined by $x_2$ because of the first equation.

You can investigate yourself what happens if you do something with the columns. It means manipulating the variables, or you avoid column operations.

 

[Mark44]

it is just normal ref but with some rows with only one variables (column)

If you're trying to get a solution to the homogeneous system, any row that has only one nonzero entry means that that variable's value is zero.

To get a basis for the null space, presumably you have some rows in which not all entries are zero. Using your example from post #1, where a row is given as {-1, 2, 0, 3, -4, 0}, an equivalent row would be {1, -2, 0, -3, 4, 0}, which would represent the equation $x_1 - 2x_2 - 3x_4 - 4x_5 = 0$. Solving for the leading variable would give $x_1$ in terms of the other three variables. Lacking any other information, $x_2, x_4,$ and $x_5$ could be treated as free variables. From the other rows with nonzero leading entries (which aren't shown), one could arrive at a basis for the nullspace.