Implementation
We will write a code that checks for the conditions laid out above for a given matrix as input and returns YES for a matrix that is diagonally dominant and NO for an input that is not diagonally dominant.
Algorithm
Our program will follow the given algorithm to check for diagonally dominant matrices.
- Initiate a loop from i=0 to i=n-1 to iterate through elements in n number of rows.
- Inside the first loop, run another loop j=0 to j=n-1 to iterate over each column in a matrix.
-
For each row,
- Find the sum of non-diagonal elements, i.e, i != j.
- Check if the sum of non-diagonal elements is greater than or equal to the diagonal element (i == j).
- If the sum is greater than the diagonal element for any row, print NO; else, print YES.
Now we will implement the algorithm given above in different programming languages.
Program in C++
We will check a 3X3 square matrix for diagonally dominant using the algorithm that we have already defined.
#include <bits/stdc++.h>
#define N 3
using namespace std;
bool isDDM(int m[N][N], int n)
{
// for each row
for (int i = 0; i < n; i++)
{
// finding sum of each row.
int sum = 0;
//for each column in a row
for (int j = 0; j < n; j++)
sum += abs(m[i][j]);
// remove the diagonal element.
sum -= abs(m[i][i]);
// check for diagonal element less
// than sum of non-diagonal element.
if (abs(m[i][i]) < sum)
return false;
}
return true;
}
int main()
{
int n = 3;
int m[N][N] = { { 4, 2, 1 },
{ 3, 5, 2 },
{ 2, 4, 7 } };
(isDDM(m, n)) ? (cout << "YES") : (cout << "NO");
return 0;
}
You can also try this code with Online C++ Compiler
Run Code
Output
YES
Program in Python3
In python, we will also primarily use two iterations, and the code will look similar to the one in C++ with a different syntax.
def isDDM(m, n) :
# for each row
for i in range(0, n) :
# sum of each row.
sum = 0
#for each collumn
for j in range(0, n) :
sum = sum + abs(m[i][j])
# removing diagonal element
sum = sum - abs(m[i][i])
# check for diagonal element less
# than sum of non-diagonal element.
if (abs(m[i][i]) < sum) :
return False
return True
n = 3
m = [[ 4, 2, 1 ],
[ 3, 5, 2 ],
[ 2, 4, 7 ]]
if((isDDM(m, n))) :
print ("YES")
else :
print ("NO")
You can also try this code with Online Python Compiler
Run Code
Output
YES
Program in Java
We can also write this algorithm using the Java programming language. We will use basic Java syntax and implementation to carry out the same process as the codes above.
import java.util.*;
class CN {
static boolean isDDM(int m[][], int n)
{
// for each row
for (int i = 0; i < n; i++)
{
//sum of each row.
int sum = 0;
//for each column
for (int j = 0; j < n; j++)
sum += Math.abs(m[i][j]);
// remove the diagonal element.
sum -= Math.abs(m[i][i]);
// check for diagonal element less
// than sum of non-diagonal element..
if (Math.abs(m[i][i]) < sum)
return false;
}
return true;
}
public static void main(String[] args)
{
int n = 3;
int m[][] = { { 4, 2, 1 },
{ 3, 5, 2 },
{ 2, 4, 7 } };
if (isDDM(m, n))
System.out.println("YES") ;
else
System.out.println("NO");
}
}
You can also try this code with Online Java Compiler
Run Code
Output
YES
You can quickly implement this algorithm in many more programming languages like JavaScript and PHP by changing the syntax accordingly. The critical part here is the algorithm and the implementation, which will remain consistent in every language.
Frequently Asked Questions
What is the use of matrix in data science?
Matrices are at the core of linear algebra, on which Machine learning and analytics algorithms heavily rely. For these reasons, matrices are also known as the 'language' of most such algorithms. Matrices are also the most reliable and obvious way of storing tabular data, primarily numeric.
Why is diagonally dominant important?
We can demonstrate the importance of diagonal dominance by comparing the iterative convergence rate of an untransformed system of Boundary Element equations with the convergence rate of an equivalent, diagonally-dominant system.
Are diagonally dominant matrices invertible?
Irreducible, diagonally dominant matrices are always invertible. Such matrices often arise in theory and applications.
Is a diagonally dominant matrix positive definite?
According to theory, if a symmetric matrix is strictly rows diagonally dominant and has strictly positive diagonal entries, it will be positive definite.
Conclusion
This article extensively discusses Diagonally Dominant Matrices and how to check whether a matrix is a diagonally dominant matrix or not. To understand the codes better, you can study articles like Basics of Python, Introduction To C++, and Basics Of Java.
Check out this problem - Subarray Sum Divisible By K
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, and 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!