Check whether a matrix is Markov matrix in C++

By Alok Singh

In this tutorial, we will learn how to check whether a matrix is a Markov matrix or not in C++ with Example, Algorithm, and a program.

Markov matrix is a matrix in which the sum of each row is exactly equal to one.

How to check whether a matrix is Markov matrix or not in C++

To check a Markov matrix we need to find the sum of each row and check whether the sum is equal to 1 or not.

Example 1: 

Consider a matrix of 4*3
input matrix: 
               0.5  0.5   0   
               0.5  0.3  0.2
                0   0.6  0.4
                1    0    0  

Sum of first row:  0.5 + 0.5 + 0 = 1
sum of second row: 0.5 + 0.3 + 0.2 = 1
sum of third row:  1 + 0 + 0 = 1

since, the sum of each rows is equal to 1,
Therefore, the matrix is Markov matrix.

Example 2: 

Consider a matrix of 3*3
input matrix:
               1 0 0
               0 1 0
               1 1 1

sum of first row: 1 + 0 + 0 = 1
sum of second row: 0 + 1 +0 = 1
sum of third row: 1 + 1 + 1 = 3

since, the sum of each rows is not equal to 3,
Therefore, the matrix is not a Markov matrix.

Algorithm to check whether a matrix is Markov matrix

  1. declare and initialize a matrix of size m*n. (where n and m are the lengths of row and column of matrix)
  2. Declare a variable “rowsum” and initialize it with zero.
  3. Find the sum of each ith row element and save to rowsum.
  4. check whether the rowsum is equal to one. if yes, then check for the remaining row. else print “Not markov matrix”
  5. if all the row sum is equal to one, then print “Markov matrix”.

C++ program to check whether a matrix is Markov matrix

#include <bits/stdc++.h> 
using namespace std;

//function to check Markov matrix
int isMarkov(float matrix[50][50], int m, int n){

    for(int i = 0; i < m; i++)
    {
        //variable to store sum of each row
        float rowsum = 0;
        for(int j = 0; j < n; j++)
            rowsum += matrix[i][j];
        
        if(rowsum != 1)
            return 0;
    }

    return 1;
}

int main(){ 
    float matrix[50][50];
    int n, m;

    //taking input in m and n for length of row and column
    cout<<"Enter the length of row of the matrix: ";
    cin >> m;
    cout<<"Enter the length of column of the matrix: ";
    cin >> n;

    //taking input in the matrix
    cout << "\nInput the element of matrix: \n";
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
            cin>>matrix[i][j];

    if (isMarkov(matrix, m, n))
        cout << "The matrix is a markov matrix"; 
    else
        cout << "The matrix is Not a markov matrix"; 
      
    return 0; 
}

Output: 

Enter the length of row of the matrix: 4
Enter the length of column of the matrix: 3

Input the element of matrix: 0.5 0.5 0
0.5 0.3 0.2
0   0.6 0.4
1    0   0

The matrix is a markov matrix.

Time Complexity: O(m*n), where m and n are lengths of row and column respectively

You may also read: 

  1. How to swap both diagonals of a matrix in C++
  2. Find sum of each row and column of a matrix in C++

Leave a Reply