Better way to test that a matrix is upper-triangular?

Question

Today, I got to thinking about how to test that a matrix was upper-triangular. So I had a try at it.

Algorithm

$\quad \quad a_{ij}=0 $ Or $i \leq j$ $\Rightarrow$ $True$

My solution is

upperTriangularMatrixQ[mat_?MatrixQ] /; Equal @@ Dimensions@mat :=
  And @@ Flatten @ MapIndexed[#1 == 0 || LessEqual @@ #2 &, mat, {2}]

Performance testing

Sample data

testMat1 = UpperTriangularize@RandomInteger[{1, 100}, {1000, 1000}];
testMat2 = RandomInteger[{1, 100}, {1000, 1000}];

Test

upperTriangularMatrixQ@testMat1 // Timing

{3.151, True}

upperTriangularMatrixQ@testMat2 // Timing

{3.978, False}

My question

Can you come up with a better performing algorithm to solve this problem?

Answer 1

You did not specify if this test should be optimized for the positive or negative case. If most of your matrices will fail the test it can be greatly beneficial to have an early exit behavior. For example if the lower left element in the matrix is not zero you can fail the matrix after a single element test! And even in the positive case the elements on or above the diagonal do not need to be checked.

Therefore I propose:

utmQ[m_?SquareMatrixQ] :=
  VectorQ[Range[Length@m - 1], m[[# + 1, ;; #]] == ConstantArray[0, #] &]

For earlier versions you can replace SquareMatrixQ with the original argument test and condition.

Timings:

Needs["GeneralUtilities`"]

false = RandomInteger[{-9, 9}, {15000, 15000}];
true = UpperTriangularize[false];

utmQ[false] // AccurateTiming
utmQ[true]  // AccurateTiming

0.000029297

0.195

mfvonh's method for comparison:

upperTriangularMatrixQ2[false] // AccurateTiming
upperTriangularMatrixQ2[true]  // AccurateTiming

0.705001

0.795001

So you see that my method is four times faster in the positive case, and potentially orders of magnitude faster in the negative case.

Answer 2

Maybe

upperTriangularMatrixQ2[mat_?MatrixQ] /; Equal @@ Dimensions@mat := 
  UpperTriangularize@mat == mat;

test = RandomInteger[{1, 100}, {1000, 1000}];
upperTriangularMatrixQ@test // AbsoluteTiming

{2.126050, False}

upperTriangularMatrixQ2@test // AbsoluteTiming

{0.003277, False}

test2 = UpperTriangularize@test;
upperTriangularMatrixQ@test2 // AbsoluteTiming

{1.706272, True}

upperTriangularMatrixQ2@test2 // AbsoluteTiming

{0.004966, True}

Answer 3

Since V 12.0 we have UpperTriangularMatrixQ:

testMat1 = UpperTriangularize @ RandomInteger[{1, 100}, {1000, 1000}];

testMat2 = RandomInteger[{1, 100}, {1000, 1000}];

UpperTriangularMatrixQ @ testMat1 // Timing

{0.000803, True}

UpperTriangularMatrixQ @ testMat2 // Timing

{0.000018, False}