21
$\begingroup$

How would you proceed if you were asked in an interview to show that B is a nonsingular matrix (in an elegant way)?

$$B= \begin{pmatrix} 1& 1.25& −0.50& 0.15\\ 0.15& 2& 1.25& −1.50\\ −0.45& 0.25& 3& 1.25\\ 0.25& −0.15& 0.25& 4\\ \end{pmatrix}$$

In my opinion, taking the time to compute the determinant of this $4\times4$ matrix during the interview would not be appreciated by the interviewer.

$\endgroup$
53
$\begingroup$

$B^T$ is non-singular because it is a strict diagonally dominant matrix. So $B$ is non-singular as well.

$\endgroup$
  • 1
    $\begingroup$ [+1} Having a look at the coefficients shows that your answer is in the spirit of this "test". A reference for the invertibility proof :(math.stackexchange.com/questions/456722/…) $\endgroup$ – Jean Marie Mar 29 '17 at 6:23
  • 2
    $\begingroup$ $|1| \overset{?}{>} |1.25| + |-0.5| + |0.15| = 1.90$? $\endgroup$ – dantopa Mar 29 '17 at 15:18
  • 4
    $\begingroup$ @dantopa You need to look at the columns not at the rows here. Then you know that the transpose of a nonsingular matrix is nonsingular. $\endgroup$ – QFi Mar 29 '17 at 15:47
  • 4
    $\begingroup$ The transpose notation is unnecessarily confusing and nonstandard. That's why people are ignoring it and getting confused about the rows. Just use $B^\top$ or something. $\endgroup$ – Mehrdad Mar 30 '17 at 2:07
  • 1
    $\begingroup$ @Mehrdad In France it is a very common notation. But I will edit since this one tends to be a problem for a lot of people here. $\endgroup$ – nicomezi Mar 30 '17 at 7:35
40
$\begingroup$

Another approach:

Multiply by a constant to make it an integer matrix: in this case, consider the matrix $20B$, which is an integer matrix. Show that its determinant is non-zero modulo some small prime, eg: 2 or 3.

$\endgroup$
  • 3
    $\begingroup$ Mod 2 works, and row reducing the mod 2 version is also easy. $\endgroup$ – Jonas Meyer Mar 29 '17 at 5:46
  • 3
    $\begingroup$ +1 While the other example is ingenious it seems like a fairly obscure (never heard of it and I have a masters in abstract algebra) theorem. This seems like the more usual approach. $\endgroup$ – DRF Mar 29 '17 at 13:22
  • 6
    $\begingroup$ @DRF It is often mentionned in numerical linear algebra courses. If you are more into abstract algebra, as you said, that may explain why you have never heard of it. $\endgroup$ – nicomezi Mar 29 '17 at 17:48
  • 1
    $\begingroup$ @Aravind Oh I see. So I still have to compute a 4 x 4 determinant, but it will have much, much simpler calculations involved (i.e. multiplying and adding/subtracting zeros and ones). $\endgroup$ – Pedro A Mar 29 '17 at 19:26
  • 2
    $\begingroup$ @Hamsteriffic: Your goal is to show the determinant is nonzero mod $2$, but that doesn't have to be by computing the determinant. Any method of proving the determinant nonzero will suffice, such as row reducing it to the identity. (although, since it's mod $2$, doing so would prove the determinant is $1$) $\endgroup$ – Hurkyl Mar 30 '17 at 8:43
2
$\begingroup$

Something that will always work with low complexity and not dependent on which matrix:

  1. Take a random vector
  2. Loop over columns / rows:
    • Remove projection with current row/col

If after three (or $n-1$) removed projections is not parallel to last vector ( up to precision ) then there is a non-zero sized null-space.

I'm very sure that the chance of accidentally hitting a subspace in the value space is abysmally small.

$\endgroup$
0
$\begingroup$

Another possibility:

Use Gaussian elimination on $B$ to yield an upper-triangular matrix. Nonzeros on the diagonal of the resulting upper-triangular matrix means that $B$ is nonsingular.

(OP asked for an elegant way to do this; however, "elegant" was not defined. IMHO, Gaussian elimination is way more elegant than computing the determinant.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.