Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Markov Matrix
3.
Problem
4.
Algorithm
4.1.
C++
4.2.
Java
4.3.
PHP
4.4.
Output
5.
Frequently Asked Questions
5.1.
Is it possible to tell if a matrix is idempotent?
5.2.
Is it true that the matrix is orthogonal?
5.3.
Is it true that a null matrix is nilpotent?
5.4.
What is the involutory matrix's inverse?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Markov Matrix

Author SHIVANGI MALL
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction 

In this article, we will learn whether a given matrix is Markov Matrix or not. Elements of the matrix are arranged in a row and column format where m* n matrix refers to a matrix that has m rows and n columns.

Individual entries in the matrix are referred to as elements, and they are represented by the symbol a[i][j], which indicates that element a is found in the ith row and jth column.

Recommended Topic, Array Implementation of Queue and  Rabin Karp Algorithm

Markov Matrix

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

                                              

Example 

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

Sum of first row:  0.4 + 0.5 + 0.1 = 1
sum of second row: 0 + 0.8 + 0.2 = 1
sum of third row:  1 + 0 + 0 = 1

since the sum of each row is equal to 1,
Therefore, the matrix is Markov matrix.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.";
}

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.")

 

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.";


?>

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 MatricesConstruct a Linked List from a 2D MatrixMatrix Chain MultiplicationBook Allocation ProblemTypes 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!

 

Previous article
Magic Square Matrix
Next article
Strassen’s Matrix Multiplication
Live masterclass