Problem
Given a m x n 2D matrix, check if it is a Markov Matrix.
Algorithm
Step 1 - START
Step 2 - Create a new 1-dimensional array namely result.
Step 3 - Iterate over the matrix using 2 for loop and store the sum of each row in temp.
Step 4 - Run one for loop from i=0 to i<n and check if temp[i]==0 then return false.
Step 5 - else when we came out of the loop return true.
Step 5 - Stop
C++
// C++ code to check Markov Matrix
#include <iostream>
using namespace std;
#define n 3
bool isMarkov(double matrix[][n])
{
// outer loop to access rows
// and inner to access columns
for (int i = 0; i <n; i++) {
// Find sum of current row
double sum = 0;
for (int j = 0; j < n; j++)
sum = sum + matrix[i][j];
if (sum != 1)
return false;
}
return true;
}
// Driver Code
int main()
{
// Matrix to check
double matrix[3][3] = { { 0.4, 0.5, 0.1 },
{ 0, 0.8, 0.2 },
{ 1, 0, 0 } };
// calls the function check()
if (isMarkov(matrix))
cout << "The matrix is a markov matrix.";
else
cout << "The matrix is not markov matrix.";
}
You can also try this code with Online C++ Compiler
Run Code
Java
// Java code to check Markov Matrix
import java.io.*;
public class markov
{
static boolean isMarkov(double matrix[][])
{
// outer loop to access rows
// and inner to access columns
for (int i = 0; i < matrix.length; i++) {
// Find sum of current row
double sum = 0;
for (int j = 0; j < matrix[i].length; j++)
sum = sum + matrix[i][j];
if (sum != 1)
return false;
}
return true;
}
public static void main(String args[])
{
// Matrix to check
double matrix[][] = { { 0.4, 0.5, 0.1 },
{ 0, 0.8, 0.2 },
{ 1, 0, 0 } };
// calls the function check()
if (isMarkov(matrix))
System.out.println("The matrix is a markov matrix.");
else
System.out.println("The matrix is not markov matrix.");
}
}
Python
# Python 3 code to check Markov Matrix
def isMarkov(matrix) :
# Outer loop to access rows
# and inner to access columns
for i in range(0, len(matrix)) :
# Find sum of current row
sm = 0
for j in range(0, len(matrix[i])) :
sm = sm + matrix[i][j]
if (sm != 1) :
return False
return True
# Matrix to check
matrix = [ [ 0.4, 0.5, 0.1 ],
[ 0, 0.8, 0.2 ],
[ 1, 0, 0 ] ]
# Calls the function check()
if (isMarkov(matrix)) :
print("The matrix is a markov matrix.")
else :
print("The matrix is not markov matrix.")
You can also try this code with Online Java Compiler
Run Code
PHP
<?php
// PHP code to check Markov Matrix
function isMarkov($matrix)
{
$n = 3;
// outer loop to access rows
// and inner to access columns
for ($i = 0; $i <$n; $i++)
{
// Find sum of current row
$sum = 0;
for ($j = 0; $j < $n; $j++)
$sum = $sum + $matrix[$i][$j];
if ($sum != 1)
return false;
}
return true;
}
// Driver Code
// Matrix to check
$matrix = array(array(0.4, 0.5, 0.1),
array(0, 0.8, 0.2),
array(1, 0, 0));
// calls the function check()
if (isMarkov($matrix))
echo "The matrix is a markov matrix.";
else
echo "The matrix is not markov matrix.";
?>
You can also try this code with Online PHP Compiler
Run Code
Output
The matrix is a markov matrix.
Time Complexity: Time complexity is O(m*n), where m and n are lengths of row and column.
Frequently Asked Questions
Is it possible to tell if a matrix is idempotent?
If and only if the matrix 'M' multiplied by itself returns the same matrix 'M,' i.e., M * M = M, a matrix 'M' is called an idempotent matrix.
Is it true that the matrix is orthogonal?
If the transpose of a square matrix with real numbers or elements equals the inverse matrix, the matrix is said to be orthogonal.
Is it true that a null matrix is nilpotent?
A nilpotent matrix is a square matrix in which the product of the matrix and itself is a null matrix.
What is the involutory matrix's inverse?
An involutory matrix is a square matrix that is its own inverse in mathematics. That is, if and only if A^2 = I, where I is the n*n identity matrix, multiplication by the matrix A is an involution.
Conclusion
This article extensively discussed whether a given matrix is Markov Matrix or not.
We hope you have learned something new from this blog. And if you're interested in learning more, see our posts on Operations On Matrices, Construct a Linked List from a 2D Matrix, Matrix Chain Multiplication, Book Allocation Problem, Types of Matrix. Please vote for our blog to help other ninjas succeed.
Visit our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more.!
Happy Reading!