Given an N*N matrix mat[][], the task is to find the sum of Eigen values of the given matrix.
Examples:
Input: mat[][] = {
{2, -1, 0},
{-1, 2, -1},
{0, -1, 2}}
Output: 6
Input: mat[][] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}}
Output: 34
Approach: The sum of Eigen values of a matrix is equal to the trace of the matrix. The trace of an n × n square matrix A is defined to be the sum of the elements on the main diagonal (the diagonal from the upper left to the lower right) of A.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 4// Function to return the sum of eigen// values of the given matrixint sumEigen(int mat[N][N]){ int sum = 0; // Calculate the sum of // the diagonal elements for (int i = 0; i < N; i++) sum += (mat[i][i]); return sum;}// Driver codeint main(){ int mat[N][N] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; cout << sumEigen(mat); return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG{ static int N = 4;// Function to return the sum of eigen// values of the given matrixstatic int sumEigen(int mat[][]){ int sum = 0; // Calculate the sum of // the diagonal elements for (int i = 0; i < N; i++) sum += (mat[i][i]); return sum;}// Driver codepublic static void main (String[] args) { int mat[][] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; System.out.println (sumEigen(mat));}}// The code is contributed by Tushil.. |
Python3
# Python3 implementation of the approachN=4# Function to return the sum of eigen# values of the given matrixdef sumEigen(mat): sum = 0 # Calculate the sum of # the diagonal elements for i in range(N): sum += (mat[i][i]) return sum# Driver codemat= [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ] ]print(sumEigen(mat))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;class GFG{ static int N = 4;// Function to return the sum of eigen// values of the given matrixstatic int sumEigen(int [,]mat){ int sum = 0; // Calculate the sum of // the diagonal elements for (int i = 0; i < N; i++) sum += (mat[i,i]); return sum;}// Driver codestatic public void Main (){ int [,]mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; Console.Write(sumEigen(mat));}}// The code is contributed by ajit... |
Javascript
<script>// Javascript implementation of the approachvar N = 4;// Function to return the sum of eigen// values of the given matrixfunction sumEigen(mat){ var sum = 0; // Calculate the sum of // the diagonal elements for (var i = 0; i < N; i++) sum += (mat[i][i]); return sum;}// Driver codevar mat = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ] ];document.write( sumEigen(mat));</script> |
Output
34
Time complexity: O(N)
Auxiliary space: O(1)
New Approach:- Here, another approach to finding the sum of eigenvalues of an N x N matrix is by using the determinant of the matrix. The determinant of a matrix can be calculated by finding the product of all the eigenvalues of the matrix. Therefore, if we can calculate the determinant of the matrix, we can find the sum of eigenvalues by taking the trace of the matrix.
The formula to calculate the determinant of an N x N matrix is:
determinant = ? (-1)i+j * Mij * det(Aij)
where i, j are the row and column indices respectively, Mij is the minor of Aij, and det(Aij) is the determinant of the (N-1) x (N-1) matrix obtained by deleting the i-th row and j-th column from the original matrix.
Algorithm :-
- Define a constant N with value 4 to represent the size of the square matrix.
- Define a function determinant() that takes the matrix and its size as input and returns its determinant.
- If the size of the matrix is 1, return its only element as its determinant.
- Define a sign variable with a value of 1 and a temp matrix with size (N-1)x(N-1).
- For each column k in the first row of the matrix, create the submatrix without the kth column and the first row and call determinant() recursively on the submatrix to get its determinant.
- Add the product of the determinant, sign and the element in the first row and the kth column to the determinant of the original matrix.
- Flip the sign of the sign variable.
- Define a function sumEigen() that takes the matrix as input and returns the sum of its eigenvalues.
- Calculate the determinant of the matrix by calling determinant() on the matrix.
- Calculate the sum of the diagonal elements of the matrix and return it as the sum of the eigenvalues of the matrix.
- In the main() function, create a 4×4 matrix and call sumEigen() on it to get the sum of its eigenvalues.
- Print the sum of the eigenvalues of the matrix.
Below is the implementation of this approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 4// Function to calculate the determinant of a matrixint determinant(int mat[N][N], int n){ int det = 0; if (n == 1) { return mat[0][0]; } int sign = 1; int temp[N][N]; for (int k = 0; k < n; k++) { int i = 0, j = 0; for (int row = 1; row < n; row++) { for (int col = 0; col < n; col++) { if (col != k) { temp[i][j++] = mat[row][col]; if (j == n - 1) { j = 0; i++; } } } } det += sign * mat[0][k] * determinant(temp, n - 1); sign = -sign; } return det;}// Function to return the sum of eigen// values of the given matrixint sumEigen(int mat[N][N]){ int det = determinant(mat, N); int sum = 0; for (int i = 0; i < N; i++) { sum += mat[i][i]; } return sum;}// Driver codeint main(){ int mat[N][N] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; cout << sumEigen(mat); return 0;} |
Java
// Java implementation of the approachimport java.util.*;public class Main { static final int N = 4; // Function to calculate the determinant of a matrix static int determinant(int mat[][], int n) { int det = 0; if (n == 1) { return mat[0][0]; } int sign = 1; int temp[][] = new int[N][N]; for (int k = 0; k < n; k++) { int i = 0, j = 0; for (int row = 1; row < n; row++) { for (int col = 0; col < n; col++) { if (col != k) { temp[i][j++] = mat[row][col]; if (j == n - 1) { j = 0; i++; } } } } det += sign * mat[0][k] * determinant(temp, n - 1); sign = -sign; } return det; } // Function to return the sum of eigen // values of the given matrix static int sumEigen(int mat[][]) { int det = determinant(mat, N); int sum = 0; for (int i = 0; i < N; i++) { sum += mat[i][i]; } return sum; } // Driver code public static void main(String args[]) { int mat[][] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; System.out.println(sumEigen(mat)); }} |
Python3
# Function to calculate the determinant of a matrixdef determinant(mat, n): det = 0 if n == 1: return mat[0][0] sign = 1 temp = [[0] * n for _ in range(n)] for k in range(n): i, j = 0, 0 for row in range(1, n): for col in range(n): if col != k: temp[i][j] = mat[row][col] j += 1 if j == n - 1: j = 0 i += 1 det += sign * mat[0][k] * determinant(temp, n - 1) sign = -sign return det# Function to return the sum of eigen values of the given matrixdef sum_eigen(mat): det = determinant(mat, len(mat)) sum_val = 0 for i in range(len(mat)): sum_val += mat[i][i] return sum_val# Driver codeif __name__ == "__main__": mat = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16] ] print(sum_eigen(mat))#This code is contributed by aeroabrar_31 |
C#
using System;public class GFG{ static readonly int N = 4; // Function to calculate the determinant of a matrix static int determinant(int[,] mat, int n) { int det = 0; if (n == 1) { return mat[0, 0]; } int sign = 1; int[,] temp = new int[N, N]; for (int k = 0; k < n; k++) { int i = 0, j = 0; for (int row = 1; row < n; row++) { for (int col = 0; col < n; col++) { if (col != k) { temp[i, j++] = mat[row, col]; if (j == n - 1) { j = 0; i++; } } } } det += sign * mat[0, k] * determinant(temp, n - 1); sign = -sign; } return det; } // Function to return the sum of eigen values of the given matrix static int sumEigen(int[,] mat) { int det = determinant(mat, N); int sum = 0; for (int i = 0; i < N; i++) { sum += mat[i, i]; } return sum; } // Driver code public static void Main() { int[,] mat = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; Console.WriteLine(sumEigen(mat)); }} |
Javascript
const N = 4;// Function to calculate the determinant of a matrixfunction determinant(mat, n) { let det = 0; if (n === 1) { return mat[0][0]; } let sign = 1; let temp = Array.from({ length: N }, () => Array(N).fill(0)); for (let k = 0; k < n; k++) { let i = 0, j = 0; for (let row = 1; row < n; row++) { for (let col = 0; col < n; col++) { if (col !== k) { temp[i][j++] = mat[row][col]; if (j === n - 1) { j = 0; i++; } } } } det += sign * mat[0][k] * determinant(temp, n - 1); sign = -sign; } return det;}// Function to return the sum of eigen values of the given matrixfunction sumEigen(mat) { const det = determinant(mat, N); let sum = 0; for (let i = 0; i < N; i++) { sum += mat[i][i]; } return sum;}// Driver code const mat = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16] ]; console.log(sumEigen(mat)); |
Output
34
“The time complexity of this approach is O(N^3) because we are using the Laplace expansion method to calculate the determinant of the matrix.
The auxiliary space complexity is O(N^2) because we are using a temporary 2D array to store the submatrix obtained after deleting the i-th row and j-th column from the original matrix.”
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
