In linear algebra, the characteristic polynomial of a square matrix is a polynomial that is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients.
The characteristic polynomial of the 3×3 matrix can be calculated using the formula
x3 – (Trace of matrix)*x2 + (Sum of minors along diagonal)*x – determinant of matrix = 0
Example:
Input: mat[][] = { { 0, 1, 2 }, { 1, 0, -1 }, { 2, -1, 0 } }
Output: x^3 – 6x + 4
Approach: Lets break up the formula and find the value of each term one by one:
Trace of the matrix
Trace of a Matrix the sum of elements along its diagonal.
Trace of Matrix
Minor of the matrix
-
- The minor of the matrix is for each element of the matrix and is equal to the part of the matrix remaining after excluding the row and the column containing that particular element. The new matrix formed with the minors of each element of the given matrix is called the minor of the matrix.
- Each new element of the minor matrix can be achieved as follows:
-
- Determinant of a Matrix is a special number that is defined only for square matrices (matrices that have the same number of rows and columns). The determinant is used at many places in calculus and another matrix-related algebra, it actually represents the matrix in terms of a real number which can be used in solving a system of linear equations and finding the inverse of a matrix.
Program to find Characteristic Polynomial of a Square Matrix
C++
// C++ code to calculate// characteristic polynomial of 3x3 matrix#include <bits/stdc++.h>using namespace std;#define N 3// Traceint findTrace(int mat[N][N], int n){ int sum = 0; for (int i = 0; i < n; i++) sum += mat[i][i]; return sum;}// Sum of minors along diagonalint sum_of_minors(int mat[N][N], int n){ return ( (mat[2][2] * mat[1][1] - mat[2][1] * mat[1][2]) + (mat[2][2] * mat[0][0] - mat[2][0] * mat[0][2]) + (mat[1][1] * mat[0][0] - mat[1][0] * mat[0][1]));}// Function to get cofactor of mat[p][q]// in temp[][]. n is current dimension of mat[][]// Cofactor will be used for calculating determinantvoid getCofactor(int mat[N][N], int temp[N][N], int p, int q, int n){ int i = 0, j = 0; // Looping for each element of the matrix for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { // Copying into temporary matrix only those // element which are not in given row and // column if (row != p && col != q) { temp[i][j++] = mat[row][col]; // Row is filled, so increase row index // and reset col index if (j == n - 1) { j = 0; i++; } } } }}// Function for calculating// determinant of matrixint determinantOfMatrix(int mat[N][N], int n){ // Initialize result int D = 0; // Base case : if matrix // contains single element if (n == 1) return mat[0][0]; // To store cofactors int temp[N][N]; // To store sign multiplier int sign = 1; // Iterate for each element of first row for (int f = 0; f < n; f++) { // Getting Cofactor of mat[0][f] getCofactor(mat, temp, 0, f, n); D += sign * mat[0][f] * determinantOfMatrix(temp, n - 1); // Terms are to be added with alternate sign sign = -sign; } return D;}// Driver Codeint main(){ // Given matrix int mat[N][N] = { { 0, 1, 2 }, { 1, 0, -1 }, { 2, -1, 0 } }; int trace = findTrace(mat, 3); int s_o_m = sum_of_minors(mat, 3); int det = determinantOfMatrix(mat, 3); cout << "x^3"; if (trace != 0) { trace < 0 ? cout << " + " << trace * -1 << "x^2" : cout << " - " << trace << "x^2"; } if (s_o_m != 0) { s_o_m < 0 ? cout << " - " << s_o_m * -1 << "x" : cout << " + " << s_o_m << "x"; } if (det != 0) { det < 0 ? cout << " + " << det * -1 : cout << " - " << det; } return 0;} |
Java
// Java code to calculate// characteristic polynomial of 3x3 matriximport java.util.*;class GFG{ static final int N =3; // Trace static int findTrace(int mat[][], int n) { int sum = 0; for (int i = 0; i < n; i++) sum += mat[i][i]; return sum; } // Sum of minors along diagonal static int sum_of_minors(int mat[][], int n) { return ( (mat[2][2] * mat[1][1] - mat[2][1] * mat[1][2]) + (mat[2][2] * mat[0][0] - mat[2][0] * mat[0][2]) + (mat[1][1] * mat[0][0] - mat[1][0] * mat[0][1])); } // Function to get cofactor of mat[p][q] // in temp[][]. n is current dimension of mat[][] // Cofactor will be used for calculating determinant static void getCofactor(int mat[][], int temp[][], int p, int q, int n) { int i = 0, j = 0; // Looping for each element of the matrix for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { // Copying into temporary matrix only those // element which are not in given row and // column if (row != p && col != q) { temp[i][j++] = mat[row][col]; // Row is filled, so increase row index // and reset col index if (j == n - 1) { j = 0; i++; } } } } } // Function for calculating // determinant of matrix static int determinantOfMatrix(int mat[][], int n) { // Initialize result int D = 0; // Base case : if matrix // contains single element if (n == 1) return mat[0][0]; // To store cofactors int [][]temp = new int[N][N]; // To store sign multiplier int sign = 1; // Iterate for each element of first row for (int f = 0; f < n; f++) { // Getting Cofactor of mat[0][f] getCofactor(mat, temp, 0, f, n); D += sign * mat[0][f] * determinantOfMatrix(temp, n - 1); // Terms are to be added with alternate sign sign = -sign; } return D; } // Driver Code public static void main(String[] args) { // Given matrix int [][]mat = { { 0, 1, 2 }, { 1, 0, -1 }, { 2, -1, 0 } }; int trace = findTrace(mat, 3); int s_o_m = sum_of_minors(mat, 3); int det = determinantOfMatrix(mat, 3); System.out.print("x^3"); if (trace != 0) { if(trace < 0) System.out.print(" + " + trace * -1+ "x^2"); else System.out.print(" - " + trace+ "x^2"); } if (s_o_m != 0) { if(s_o_m < 0 ) System.out.print(" - " + s_o_m * -1+ "x"); else System.out.print(" + " + s_o_m+ "x"); } if (det != 0) { if(det < 0 ) System.out.print(" + " + det * -1); else System.out.print(" - " + det); } }}// This code is contributed by Rajput-Ji |
Python3
# JavaScript code for the above approachN = 3# Tracedef findTrace(mat, n): sum = 0 for i in range(n): sum += mat[i][i] return sum# Sum of minors along diagonaldef sum_of_minors(mat, n): return ((mat[2][2] * mat[1][1] - mat[2][1] * mat[1][2]) + (mat[2][2] * mat[0][0] - mat[2][0] * mat[0][2]) + (mat[1][1] * mat[0][0] - mat[1][0] * mat[0][1]))# Function to get cofactor of mat[p][q]# in temp[][]. n is current dimension of mat[][]# Cofactor will be used for calculating determinantdef getCofactor(mat, temp, p, q, n): i,j = 0,0 # Looping for each element of the matrix for row in range(n): for col in range(n): # Copying into temporary matrix only those # element which are not in given row and # column if (row != p and col != q): temp[i][j] = mat[row][col] j += 1 # Row is filled, so increase row index # and reset col index if (j == n - 1): j = 0 i += 1# Function for calculating# determinant of matrixdef determinantOfMatrix(mat, n): # Initialize result D = 0 # Base case : if matrix # contains single element if (n == 1): return mat[0][0] # To store cofactors temp = [[0 for i in range(n)] for j in range(n)] # To store sign multiplier sign = 1 # Iterate for each element of first row for f in range(n): # Getting Cofactor of mat[0][f] getCofactor(mat, temp, 0, f, n) D += sign * mat[0][f] * determinantOfMatrix(temp, n - 1) # Terms are to be added with alternate sign sign = -sign return D# Driver Code# Given matrixmat = [[0, 1, 2], [1, 0, -1], [2, -1, 0]]trace = findTrace(mat, 3)s_o_m = sum_of_minors(mat, 3)det = determinantOfMatrix(mat, 3)print("x^3",end="")if (trace != 0): print(f" {trace * -1}x^2",end="") if(trace < 0) else print(f" - {trace}x^2",end="")if (s_o_m != 0): print(f" - {s_o_m * -1}x",end="") if(s_o_m < 0) else print(f" + {s_o_m}x",end="")if (det != 0): print(f" + {det * -1}",end="") if (det < 0) else print(f" - {det}",end="")# This code is contributed by shinjanpatra |
C#
// C# code to calculate// characteristic polynomial of 3x3 matrixusing System;class GFG { static int N = 3; // Trace static int findTrace(int[, ] mat, int n) { int sum = 0; for (int i = 0; i < n; i++) sum += mat[i, i]; return sum; } // Sum of minors along diagonal static int sum_of_minors(int[, ] mat, int n) { return ( (mat[2, 2] * mat[1, 1] - mat[2, 1] * mat[1, 2]) + (mat[2, 2] * mat[0, 0] - mat[2, 0] * mat[0, 2]) + (mat[1, 1] * mat[0, 0] - mat[1, 0] * mat[0, 1])); } // Function to get cofactor of mat[p][q] // in temp[][]. n is current dimension of mat[][] // Cofactor will be used for calculating determinant static void getCofactor(int[, ] mat, int[, ] temp, int p, int q, int n) { int i = 0, j = 0; // Looping for each element of the matrix for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { // Copying into temporary matrix only those // element which are not in given row and // column if (row != p && col != q) { temp[i, j++] = mat[row, col]; // Row is filled, so increase row index // and reset col index if (j == n - 1) { j = 0; i++; } } } } } // Function for calculating // determinant of matrix static int determinantOfMatrix(int[, ] mat, int n) { // Initialize result int D = 0; // Base case : if matrix // contains single element if (n == 1) return mat[0, 0]; // To store cofactors int[, ] temp = new int[N, N]; // To store sign multiplier int sign = 1; // Iterate for each element of first row for (int f = 0; f < n; f++) { // Getting Cofactor of mat[0][f] getCofactor(mat, temp, 0, f, n); D += sign * mat[0, f] * determinantOfMatrix(temp, n - 1); // Terms are to be added with alternate sign sign = -sign; } return D; } // Driver Code public static void Main() { // Given matrix int[, ] mat = { { 0, 1, 2 }, { 1, 0, -1 }, { 2, -1, 0 } }; int trace = findTrace(mat, 3); int s_o_m = sum_of_minors(mat, 3); int det = determinantOfMatrix(mat, 3); Console.Write("x^3"); if (trace != 0) { if (trace < 0) Console.Write(" + " + trace * -1 + "x^2"); else Console.Write(" - " + trace + "x^2"); } if (s_o_m != 0) { if (s_o_m < 0) Console.Write(" - " + s_o_m * -1 + "x"); else Console.Write(" + " + s_o_m + "x"); } if (det != 0) { if (det < 0) Console.Write(" + " + det * -1); else Console.Write(" - " + det); } }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach let N = 3 // Trace function findTrace(mat, n) { let sum = 0; for (let i = 0; i < n; i++) sum += mat[i][i]; return sum; } // Sum of minors along diagonal function sum_of_minors(mat, n) { return ( (mat[2][2] * mat[1][1] - mat[2][1] * mat[1][2]) + (mat[2][2] * mat[0][0] - mat[2][0] * mat[0][2]) + (mat[1][1] * mat[0][0] - mat[1][0] * mat[0][1])); } // Function to get cofactor of mat[p][q] // in temp[][]. n is current dimension of mat[][] // Cofactor will be used for calculating determinant function getCofactor(mat, temp, p, q, n) { let i = 0, j = 0; // Looping for each element of the matrix for (let row = 0; row < n; row++) { for (let col = 0; col < n; col++) { // Copying into temporary matrix only those // element which are not in given row and // column if (row != p && col != q) { temp[i][j++] = mat[row][col]; // Row is filled, so increase row index // and reset col index if (j == n - 1) { j = 0; i++; } } } } } // Function for calculating // determinant of matrix function determinantOfMatrix(mat, n) { // Initialize result let D = 0; // Base case : if matrix // contains single element if (n == 1) return mat[0][0]; // To store cofactors let temp = new Array(n) for (let i = 0; i < temp.length; i++) { temp[i] = new Array(n) } // To store sign multiplier let sign = 1; // Iterate for each element of first row for (let f = 0; f < n; f++) { // Getting Cofactor of mat[0][f] getCofactor(mat, temp, 0, f, n); D += sign * mat[0][f] * determinantOfMatrix(temp, n - 1); // Terms are to be added with alternate sign sign = -sign; } return D; } // Driver Code // Given matrix let mat = [[0, 1, 2], [1, 0, -1], [2, -1, 0]]; let trace = findTrace(mat, 3); let s_o_m = sum_of_minors(mat, 3); let det = determinantOfMatrix(mat, 3); document.write("x^3"); if (trace != 0) { trace < 0 ? document.write(" + " + trace * -1 + "x^2") : document.write(" - " + trace + "x^2"); } if (s_o_m != 0) { s_o_m < 0 ? document.write(" - " + s_o_m * -1 + "x") : document.write(" + " + s_o_m + "x"); } if (det != 0) { det < 0 ? document.write(" + " + det * -1) : document.write(" - " + det); }// This code is contributed by Potta Lokesh </script> |
Output
x^3 - 6x + 4
Time complexity: O(N3), where N is the size of a square matrix
Auxiliary Space: O(N)
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!
