C++で行列が下三角行列かどうかを判定するプログラム

行数 r と列数 c が等しい(r = c)正方行列 M[r][c] が与えられたとき、その行列 M が「下三角行列」であるかどうかを判定する方法を解説します。

下三角行列とは

下三角行列とは、主対角線(およびその下側)の要素が非ゼロであり、主対角線より上側の要素がすべてゼロである行列のことです。

次の図の例を見てみましょう。

上の図で赤く強調されている要素は主対角線より上側の要素で、これらはすべてゼロになっています。それ以外の要素は非ゼロです。

入力例と出力例

Input: m[3][3] = { {1, 0, 0},
   {2, 3, 0},
   {4, 5, 6}}
Output: yes(下三角行列である)
Input: m[3][3] = { {3, 0, 1},
   {6, 2, 0},
   {7, 5, 3} }
Output: no(下三角行列ではない)

アルゴリズム

開始
ステップ1 → マクロを #define size 4 として定義する
ステップ2 → 行列が下三角行列かどうかを判定する関数を宣言する
   bool check(int arr[size][size])
      ループ(int i = 0; i < size; i++)
         ループ(int j = i + 1; j < size; j++)
            もし(arr[i][j] != 0)ならば
               false を返す
            終了
         終了
      終了
   true を返す
ステップ3 → main() 関数内で
   配列 int arr[size][size] = { { 1, 0, 0, 0 },
      { 2, 3, 0, 0 },
      { 4, 5, 6, 0 },
      { 7, 8, 9, 10 } } を宣言する
   もし(check(arr))ならば
      「下三角行列である」と出力する
   そうでなければ
      「下三角行列ではない」と出力する
終了

C++サンプルコード

#include <bits/stdc++.h>
#define size 4
using namespace std;
// 行列が下三角行列かどうかを判定する
bool check(int arr[size][size]){
   for (int i = 0; i < size; i++)
      for (int j = i + 1; j < size; j++)
         if (arr[i][j] != 0)
            return false;
   return true;
}
int main(){
   int arr[size][size] = { { 1, 0, 0, 0 },
      { 2, 3, 0, 0 },
      { 4, 5, 6, 0 },
      { 7, 8, 9, 10 } };
   if (check(arr))
      cout << "its a lower triangular matrix";
   else
      cout << "its not a lower triangular matrix";
   return 0;
}

出力結果

its a lower triangular matrix

仕組みの解説

このプログラムでは、二重ループを使って主対角線より上側の要素、つまり列番号 j が行番号 i より大きい位置の要素だけを走査します。一つでも非ゼロの要素が見つかった時点で、その行列は下三角行列ではないため即座に false を返します。すべての上側要素がゼロであれば true を返し、下三角行列であると判定できます。

計算量は O(n²) ですが、実際には上三角部分のみを調べるため無駄な比較がなく、効率的な実装となっています。