CODEWITHSUNDEEP
c++for-loopwhile-looptriangular
user1824947
user1824947

Reputation: 21

Check if matrix is upper triangular (c++)

I have been trying to write code that determines if a matrix is upper triangular or not, and print it.

I have tried while loops, double for loops, nothing. Here is the mess I currently have: 

int i, j;
int count = 0;
bool upper;

while (upper = true;)
{
for (i=1; i<m; i++)
{
   for (j=i-1; j<n; j++)
   {
      if (a[i] > a[j] && a[i][j] == 0.0)
         upper = true;
      else if (a[i][j] != 0.0)
         upper = false;
   }
}
}
//   cout << "Matrix is upper triangular. " << count << endl;

Upvotes: 2

Views: 4904

Answers (4)

WhozCraig
WhozCraig

Reputation: 66254

I think this will likely do what you're looking for. Note: this assume the matrix is square. If it is not (i.e. m!=n) you should return false immediately:

bool upper = true;
for (i=1; i<m && upper; ++i)
   for (j=0; j<i && (upper = (0 == a[i][j])); ++j);

Upvotes: 1

Nikos C.
Nikos C.

Reputation: 51920

Whether the matrix is upper triangular or not can only be determined by checking the whole lower part. If you encounter a non-zero element along the way, you know it's not upper triangular. You cannot make that determination until you checked the whole lower part. So your:

upper = true;

statement while you're still in the loop has no logical basis.

The problem is similar to a character search inside a string. You need to check the whole string. If you arrived at the end of the string and still didn't find the character you're looking for, then (and only then) do you know that the character isn't in the string. The only difference with the matrix problem is that you've now got one additional dimension. Or, in other words, multiple one-dimensional arrays, each one +1 in size compared to the previous array, and you got to search them all.

Upvotes: 1

david
david

Reputation: 580

Have you considered using a matrix library that has this function built in? I use the Eigen library quite often and I find the syntax very easy to use - they also have a short and useful tutorial to become familiar rather quickly.

http://eigen.tuxfamily.org/index.php?title=Main_Page

Upvotes: 0

PiotrNycz
PiotrNycz

Reputation: 24430

Look at example:

 |0|1|2|3|4|5|
0| | | | | | |
1|X| | | | | |
2|X|X| | | | |
3|X|X|X| | | |
4|X|X|X|X| | |
5|X|X|X|X|X| |

This matrix is upper triangular is cells marked with X are all zero.
For i-th row - the cells {i,0},{i,1}, ... , {i,i-1} must be zero.

So it is easy task:

bool isUpperTriangle = true; // be optimistic!
for (int i = 1; i < SIZE && isUpperTriangle; ++i) // rows
    for (int j = 0; j < i && isUpperTriangle; ++j) // columns - see example
        if (m[i][j] != 0) 
            isUpperTriangle = false;

Upvotes: 1

Related Questions