Null space of square matrix $A$ by using Gaussian Elimination - How?

Question

I have a matrix:

$$A = \begin{bmatrix} 23.941& 30.000& 20.000& 14.000 \\ 30.000& 49.941& 32.000& 49.000\\ 20.000& 32.000& 20.941& 32.000\\ 14.000& 49.000& 32.000& 108.941 \end{bmatrix}$$

And I want to find the null space by using gaussian elimination.

First of all, I know that the null vector is: (and my goal is to find the eigenvectors from $A$ where I already know the eigenvalues! This vector is one eigenvector)

$$x = \begin{bmatrix} 0.40870 \\ 0.20893\\ -0.88130\\ 0.11237 \end{bmatrix}$$

I first do gaussian elimination so my matrix looks like this:

$$A = \begin{bmatrix} 23.940999984741210938& 30.000000000000000000& 20.000000000000000000& 14.000000000000000000\\ 0.000000000000000000& 12.348587036132812500& 6.938390731811523438& 31.456872940063476562\\ 0.000000000000000000& 0.000000000000000000& 0.334734916687011719& 2.629678726196289062\\ 0.00000000000000000& 0.000000000000000000& 0.000000000000000000& -0.038000106811523438 \end{bmatrix}$$

Notice that I have using an algoritm for this!

Now what next? I have my matrix and I have reduce it to upper triangular. Can I find the null space now? What can I do with the number $A(4,4) = -0.038000106811523438$?

I update my question:

>> B % We start with this matrix
B =

  -2.62801   0.37593   0.12769
   0.37593  -4.71395  -1.05542
   0.12769  -1.05542  -0.23703

>> x = null(B) % We can find the null vector here
x =

   0.016349
  -0.217213
   0.975987

>> B*x % We can see that B*x will become zero, at least very close to zero
ans =

   4.1633e-17
  -2.2204e-16
   1.1380e-15

>> [u, s, v] = svd(B); % Or we can look at the last u column
>> u(:, 3)
ans =

   0.016349
  -0.217213
   0.975987

>>

You are trying to solve $Ax=0$. Just proceed like usual from the last step like you would for solving any system of equations. — Simply Beautiful Art, Mar 30 '20 at 01:03
Since the RREF has full rank, the null space consists only of the zero vector. Have you actually verified that $x$ is a null vector of $A$ by direct multiplication, or that $A$ is rank-deficient in the first place? Even if it’s supposed to be, the entries of $A$ look like they’re approximate values, so trying for an exact solution via Gaussian elimination is likely to fail. You’ll probably have to resort to an approximation, such as taking the singular vector that corresponds to the least singular value of $A$. — amd, Mar 30 '20 at 01:05
Indeed, and if you continue from there you will get all possible null vectors. — Simply Beautiful Art, Mar 30 '20 at 01:08
@amd can I solve this with SVD or QR? Only looking for square matrecies — euraad, Mar 30 '20 at 01:08
Check for yourself: the determinant of $A$ is equal to -3.755, so it has no null vectors, just as your RREF indicates. You might want to look up the Octave documentation to see what it gives you for a full-rank matrix. As well, if you compute $Ax$, you get a vector with entries that have values in the ten-thousandths, but far from zero. — amd, Mar 30 '20 at 01:09
@amd Hmmmm. Perhaps I used wrong matrix. But you probably understand what I want to do? Use Gaussian Elimination on a square matrix. Then what? — euraad, Mar 30 '20 at 01:12
Getting to roughly the same point as amd, why can't it be zero? For whatever you claim it to be, the provided problem has an invertible $A$, so there are no other solutions. You should add more information e.g. where is $A$ coming from, how did you get that $x$ precisely, and so on. — Simply Beautiful Art, Mar 30 '20 at 01:14
Once you have the RREF (which you don’t have yet), you can use the method described here to extract a basis for the null space. However, you’re still left with the problem that, because of truncated data, the matrix that you’re starting with isn’t likely to be singular. — amd, Mar 30 '20 at 01:15
Checking the SVD of $A$, your vector $x$ is indeed the singular vector that corresponds to the least singular value, but that singular value is nonzero. Using the SVD in this way is a common method for estimating a null vector from a matrix that has inexact data. No doubt that’s what Octave does when presented with a nonsingular matrix. — amd, Mar 30 '20 at 01:17
your matrix is symmetric. That says, among other things, that (with four distinct eigenvalues) that the eigenvectors are orthogonal — Will Jagy, Mar 30 '20 at 01:26
Taking the matrix with diagonal elements truncated to be integers, the eigenvalues are [-0.9414783936142500585321428603, 0.1969882956881690273387610862, 42.34682104487864036287791134, 158.3976690530474406683154704] so you have added $0.9414783936142500585321428603 I$ and thus shifted the smallest eigenvalue to zero, without changing the eigenvectors. — Will Jagy, Mar 30 '20 at 01:32

amd · Accepted Answer · 2020-03-30T18:22:28.567

You’ve got a bit of a problem here since the reduced matrix clearly has full rank, so its only null vector is $0$. Indeed, the original matrix $A$ is nonsingular: its determinant is equal to $-3.755$, so it’s not even close. Also, if you compute $Ax$, you’ll find that its elements, though small, aren’t particularly close to zero. Their first three places after the decimal point are zero, though, so at the limit of precision that you’ve got in the original data, it could be considered a null vector.

When working with inexact data like this, even if you know theoretically that the matrix should be singular, the actual matrix that you work with might turn out not be so in practice. On top of that, Gaussian elimination isn’t a particularly stable algorithm, so it can introduce its own errors as well. A common way to deal with this is to approximate a null vector of the matrix by computing its SVD (singular value decomposition) and then taking the right singular vector that corresponds to the smallest singular value. It appears that this is what Octave did. Computing the SVD of $A$ in Mathematica yields $(0.408695,0.208933,-0.881299,0.112373)$ for this, which jibes with the vector $x$ in your question. The corresponding singular value is $0.000478394$, which, since the matrix is symmetric, has the same absolute value as its least-modulus eigenvalue. This is zero to three places, which is about as good as the input data that you have.

In Matlab, you can compute the SVD of a matrix by using the function svd, not surprisingly. See the documentation for how to interpret its results. Since you’re looking for a right null vector, you’ll need to extract a singular vector from the “$V$” matrix—the right-hand one.

Will Jagy’s observation that your matrix $A$ appears to be an integer matrix plus a multiple of the identity leads me to suspect that the underlying problem that you’re trying to solve is finding eigenvectors of the integer matrix $$B=\begin{bmatrix}23&30&20&14\\30&49&32&49\\20&32&20&32\\14&49&32&103\end{bmatrix}$$ and indeed, to three decimal places one of its eigenvalues is $-0.941$. However, this is not a very well-conditioned matrix and the one you obtained by adding $0.941\,I$ to it is even worse. What this means is that it’s going to be very sensitive to truncation and other sources of error. Try this experiment: see what happens to the value of the determinant of $B-\lambda I$ as you add more and more significant digits to the approximation of this eigenvalue: carrying more precision in the approximation to the eigenvalue gets us closer and closer to singularity. Unfortunately, this also makes the matrix more and more ill-conditioned, which is bad news for Gaussian elimination. Indeed, when doing this same experiment with row-reduction instead of determinants, Mathematica eventually starts throwing warnings that the result of RowReduce may contain significant numerical errors.

From the reduced matrix in your question it looks like you’re actually carrying more precision in your calculations than you have in the matrix $A$ in your question, but if the digits after the $23$ in the reduced matrix are the more precise value that you got for this eigenvalue, then it’s off by quite a bit. That’s also going to throw off your calculations, so you might want to double-check how you’re computing eigenvalues.

Taking the matrix with diagonal elements truncated to be integers, the eigenvalues are [-0.9414783936142500585321428603, 0.1969882956881690273387610862, 42.34682104487864036287791134, 158.3976690530474406683154704] so the OP has added 0.9414783936142500585321428603 and thus shifted the smallest eigenvalue to zero, without changing the eigenvectors. I guess you and he are discussing computer commands.... — Will Jagy, Mar 30 '20 at 02:14
Great! I have try to understand your question. Do you mean that I could only take a look at the last column of $U$ from the SVD? See my updated answer! Thank you! — euraad, Mar 30 '20 at 12:38
Is it always the $u$ column? Or could it be $v$ column as well? How do I know that? — euraad, Mar 30 '20 at 12:41
I did notice now that if $A$ is symmetrical, then we need to look at the last $U$ column. If $A$ is non-symmetrical. Then we need to look at the last $V$ column. Correct me if I'm wrong. — euraad, Mar 30 '20 at 12:46
@DanielMårtensson You’re wrong. Note that the SVD exists for any shape matrix, not only for square ones. You’re looking for a right null vector, so you have to use the right singular vectors, i.e., the $V$ matrix. This would be much more obvious if your matrix wasn’t square: $U$ would clearly be the wrong size for right null vectors. If the matrix is symmetric, then $U$ and $V$ are, up to changes of sign, the same, which is why using $U$ worked for you. — amd, Mar 30 '20 at 17:41
Aha! Good to know that I'm going to look for the last column in $V$. Thank you so much. Yes! I'm trying to find the eigenvectors of a matrix. I wrote that in my question :) Are you recommending me to use SVD instead of anything else? — euraad, Mar 30 '20 at 18:10
@DanielMårtensson If you’re going to go the route of computing eigenvalues and then finding null vectors of $A-\lambda I$, then, yes. Gaussian elimination is a notoriously unstable algorithm, and you’ll be applying it to near-singular matrices, which are especially sensitive to various kinds of errors. — amd, Mar 30 '20 at 18:15

Null space of square matrix $A$ by using Gaussian Elimination - How?

1 Answers1