# What is the fastest way to find if a real nonsquare matrix is injective?

**URL:** https://discourse.julialang.org/t/what-is-the-fastest-way-to-find-if-a-real-nonsquare-matrix-is-injective/112176
**Category:** Performance
**Tags:** question, linearalgebra
**Created:** [March 27, 2024, 11:19am UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-to-find-if-a-real-nonsquare-matrix-is-injective/112176 "2024-03-27T11:19:38Z")
**Posts on this page:** 1
**Showing post:** 3

<div class="post-metadata">

### Author: ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [March 27, 2024, 12:20pm UTC](https://discourse.julialang.org/t/what-is-the-fastest-way-to-find-if-a-real-nonsquare-matrix-is-injective/112176/3 "2024-03-27T12:20:04Z")

</div>

> [@marcsgil](#):
>
> I know that I could calculate the determinant of A^\dagger A and check if its zero or not, but I have a feeling that this method is probably very inefficient.

This is quite efficient (probably much faster than SVD or QR), but is terrible for other reasons:

1. The determinant will rarely be exactly zero because roundoff errors make it difficult to distinguish singular from near-singular matrices.
2. In consequence of (1), for a near-singular matrix, you want to check that the determinant is small rather than zero, but small compared to what? (See below.)
3. Determinants of large matrices can easily overflow the largest representable floating-point value (though you can use [`logabsdet`](https://docs.julialang.org/en/v1/stdlib/LinearAlgebra/#LinearAlgebra.logabsdet) to avoid this).
4. Computing A^\dagger A = \overline{A^T} A (also denoted A^\* A) squares the condition number of A and exacerbates roundoff errors. SVD and QR methods (below) avoid computing this matrix explicitly.

> [@ctkelley](#):
>
> A small singular value (ie near roundoff) tells you that there’s trouble.

Right, but be careful — you should check for small singular values compared to the largest singular value. (There is no such thing as “small” in an absolute sense — it’s always important to ask “small _compared to what?_”)

Of course, comparing the smallest singular value to the largest singular value is the same as computing the [condition number](https://en.wikipedia.org/wiki/Condition_number#Matrices) of the matrix, which you can do with [`cond`](https://docs.julialang.org/en/v1/stdlib/LinearAlgebra/#LinearAlgebra.cond). If `cond(A)` is \gg 1 then the matrix is close to rank-deficient.

(Alternatively, you can call the [`rank`](https://docs.julialang.org/en/v1/stdlib/LinearAlgebra/#LinearAlgebra.rank) function, which counts the _number_ of singular values that are not too small compared to the largest one, but if you just want to check that it is full rank I would simply look at the condition number.)

(Both `cond` and `rank` use the SVD.)

> [@ctkelley](#):
>
> A rank revealing QR would be faster, but I don’t know if there is one of these in Julia.

Yes, Julia has pivoted QR, and you can use this to estimate the rank, though in principle the SVD-based methods are more reliable. See [How to find the linearly independent columns (rows) of a matrix - #14 by stevengj](https://discourse.julialang.org/t/how-to-find-the-linearly-independent-columns-rows-of-a-matrix/109772/14) and [rank(::QRPivoted) method? · Issue #53214 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/53214).

You could also use QR to compute the condition number, since if A = QR then \mathrm{cond}(A) = \mathrm{cond}(R) in exact arithmetic, and `cond(qr(A, ColumnNorm()).R)` should be faster than `cond(A)` (via the SVD) for a very “tall” matrix.

---

_[View the full topic](https://discourse.julialang.org/t/what-is-the-fastest-way-to-find-if-a-real-nonsquare-matrix-is-injective/112176)._