Logical Matrix .... Solution

Question

Suppose you have an NxN matrix and you have to check whether it's a upper diagonal matrix or not. Is there any generic method to solve this problem?

I am elaborating my question: Some thing is like this: Suppose you have NXN matrix having the value of N=4 then matrix will look like this:

|5 6 9 2|
|1 8 4 9|
|5 8 1 6|
|7 6 3 2|

Its a 4X4 square matrix and again if it's upper triangle matrix it will look something like this:

|5 6 9 2|
|1 8 4 0|
|5 8 0 0|
|7 0 0 0|

I need to generate a generic program in any language to check wether a square matrix is upper trailgle or not.

Answer 1

If you want a simplistic solution (using 1-based indexes):

def isUpperDiag(matrix[][]):
    if matrix.height != matrix.width:
        return false                      # must be square
    if matrix.height == 1:
        return true                       # not sure how to treat 1x1
    for row = 2 to matrix.height:
        for col = matrix.width - row + 2 to matrix.width:
            if matrix[row][col] != 0:
                return false
    return true

This is assuming zeros are allowed in the upper left. If not, you'd have to check that as well.

Reasonably simple. On your 4x4 matrix, it iterates row from 2 to 4 inclusive. For row 2, it iterates column from 4 to 4 inclusive. For row 3, it iterates column from 3 to 4 inclusive. For row 4, it iterates column from 2 to 4 inclusive.

At every one of those cells, it just checks that the number is zero. If not, it's not upper left triangular. If all cells checked are zero, then it is.

Answer 2

Just to check, are (1,1) the lower left and (n,n) the upper right in these diagrams? (This is not the way matrices are usually written!).

In any event, the algorithm is O(N^2) no matter what, I think -- you have to do something with all of the n*(n-1)/2 possibly-zero entries with row>column. You just have to step through them and see if they are zero -- of course, you should work your way through the matrix in the most efficient way, which depends on whether it is stored column- or row-major.

Also, is your matrix really filled with integers, or do you need to check for being approximately zero?

Basically you need to check

for col = 2, n 
   for row = col+1, n
      if matrix(row, col) != 0
         return false
      endif
   endfor
endfor

although the corner-case checks from @paxdiablo are a good idea.

Answer 3

Assuming this is feasible in your case, you could go for a classical strategy of trading time for space.

(I am assuming you are using an OO language - the idea holds for non-OO ones too, but will require more effort to ensure that the different representation of the same matrix are kept in synch).

Instead of representing the matrix as an array (or along with that representation) what about keeping it as a set of non-zero values?

So what you are representing as:

|5 6 9 2|
|1 8 4 0|
|5 8 0 0|
|7 0 0 0|

would become (or stored also as)

1,1=5
1,2=6
1,3=9
...
4,1=7

if this is doable, you could also split this set in two (upper and lower diagonal)

so in the case of your first matrix:

|5 6 9 2|
|1 8 4 9|
|5 8 1 6|
|7 6 3 2|

would be:

UpperMap -

1,1=5
1,2=6
1,3=9
...
4,1=7

Lower Map-

2,4=9
3,3=1
...
4,4=2

In this case, your test would be "asking if the lower hashmap is empty".

As mentioned above, if you need to do more "traditional" operations on the matrix you could store it as an array along with the 2-maps, and in case the matrixes are not immutable, you will have to provide methods to change the "cell" values.

The other trade off (apart from space) is that creating a new matrix requires more cpu time. But could be worth it if you create and modify these infrequently and have to test for the lower diagonal often.

A more extreme approach:

For each matrix build a bitmap representation (non-zero cells are 1, zero cells get a 0) and use logical operations to check for "emptiness" of a section.