Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Diagonally Dominant Matrix
2.1.
Example
3.
Implementation
3.1.
Algorithm
3.2.
Program in C++
3.2.1.
Output
3.3.
Program in Python3
3.3.1.
Output
3.4.
Program in Java
3.4.1.
Output
4.
Frequently Asked Questions
4.1.
What is the use of matrix in data science?
4.2.
Why is diagonally dominant important?
4.3.
Are diagonally dominant matrices invertible?
4.4.
Is a diagonally dominant matrix positive definite?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Diagonally Dominant Matrix

Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

Matrix or matrices are a potent tool for quick approximations of complicated calculations in computer science and mathematics. A matrix is a set of numbers in the form of rows and columns where numbers may represent data or mathematical equations.

We are going to learn about the Diagonally Dominant matrix through this article. We will explore the concepts, algorithms, and examples of diagonally dominant matrices with implementations in multiple programming languages.

Must Read, Array Implementation of Queue and  Rabin Karp Algorithm

Diagonally Dominant Matrix

We can call a square matrix diagonally dominant if, for every row in the matrix, the magnitude of the diagonal entry in a row is larger than or equal to the sum of the magnitudes of all the non-diagonal entries row. In simpler words, if the sum of elements in a matrix other than the diagonal element is less than the diagonal matrix. 

If We have a square matrix with i rows and j columns, we can denote this as a diagonally dominant matrix using a mathematical equation as:

Example

The following is an elementary example of a diagonally dominant matrix.

Here A is a diagonally dominant matrix because it satisfies the following:

|a11| ≥ |a12| + |a13| == |+4| ≥ |+2| + |+1|

|a22| ≥ |a21| + |a23| == |+5| ≥ |+3| + |+2|

|a33| ≥ |a31| + |a32| == |+7| ≥ |+2| + |+4|

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

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.

  1. Initiate a loop from i=0 to i=n-1 to iterate through elements in n number of rows.
  2. Inside the first loop, run another loop j=0 to j=n-1 to iterate over each column in a matrix.
  3. For each row, 
    1. Find the sum of non-diagonal elements, i.e, i != j.
    2. Check if the sum of non-diagonal elements is greater than or equal to the diagonal element (i == j).
    3. 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;
}

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

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

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 PythonIntroduction 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 MatricesConstruct a Linked List from a 2D MatrixMatrix 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!

Previous article
Check Diagonal Matrix and Scalar Matrix
Next article
Unique elements in a Matrix
Live masterclass