We have to find a Matrix of order 3 formed by given 9-elements whose determinant is maximum.
Examples:
Input: arr[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9} Max determinant possible = 412 Matrix Resulting max determinant = { 9, 4, 2, 3, 8, 6, 5, 1, 7 } Input: arr[3][3] = { 0, 2, 3, 4, 2, 6, 1, 8, 7} Max determinant possible = 315 Matrix Resulting max determinant = { 8, 2, 1, 2, 7, 4, 3, 0, 6 }
RECOMMENDED: Maximum Length Subsequence from Ticket Prices Array
Naive Approach:
Time complexity for Calculating Determinant of a matrix is O(n^3) and total different possible matrices of order 3 is 9!
So for calculating Determinant for each matrix and finally finding up the maximum is a very tough, space and time taking job.
Efficient Approach:
First of all mark positions of elements in final matrix as:
{a11, a12, a13, a21, a22, a23, a31, a32, a33}
All elements in sorted order as:
A0 < A1 < A2 < A3 < A4 < A5 < A6 < A7 < A8.
As we known that in any matrix the product of diagonal elements always leads to positive value as per their position. So we should make all three maximum value as the diagonal elements starting from the top left corner.
So we have:
a11 = A8, a22 = A7, a33 = A6.
Further if we arrange all elements as:
a23 = A5, a12 = A3, a13 = A1, a31 = A4, a21 = A2 & a32 = A0.
We should get maximum value of determinant.
Final Matrix resulting maximum Determinant =
{A8, A3, A1, A2, A7, A5, A4, A0, A6}
Maximum Determinant
= A0*A1*A2 + A3*A4*A5 + A6*A7*A8 – A0*A5*A8 – A2*A3*A6 – A1*A4*A7
Time Complexity: O(n^3), i.e., only for calculating determinant.
Algorithm:
// sort all 9 elements sort ( arr,arr+9); // fix all elements as per position result[0][0] = arr[8]; result[1][1] = arr[7]; result[2][2] = arr[6]; result[1][2] = arr[5]; result[0][1] = arr[3]; result[0][2] = arr[1]; result[2][0] = arr[4]; result[1][0] = arr[2]; result[2][1] = arr[0]; // calculate the determinant as per obtained formula det = arr[0] * arr[1] * arr[2] + arr[3] * arr[4] * arr[5] + arr[6] * arr[7] * arr[8] – arr[0] * arr[5] * arr[8] – arr[2] * arr[3] * arr[6] – arr[1] * arr[4] * arr[7]; //print the resultant matrix cout << "Required Matrix :n"; for (int i = 0; i < 3; i++) { for(int j = 0; j < 3; j++) cout << result[i][j] << " "; cout << "n"; } // print the maximum determinant value cout<<"Maximum determinant = " << det;
Implementation in C++:
// C++ program for finding a matrix // resulting in the maximum determinant #include <bits/stdc++.h> using namespace std; // Function to calculate the maximum determinant matrix void findMaxDeterminant(int arr[]) { int det, result[3][3]; // Sort all 9 elements sort(arr, arr + 9); // Fix all elements as per position result[0][0] = arr[8]; result[1][1] = arr[7]; result[2][2] = arr[6]; result[1][2] = arr[5]; result[0][1] = arr[3]; result[0][2] = arr[1]; result[2][0] = arr[4]; result[1][0] = arr[2]; result[2][1] = arr[0]; // Calculate the determinant using the obtained formula det = arr[0] * arr[1] * arr[2]; det += arr[3] * arr[4] * arr[5]; det += arr[6] * arr[7] * arr[8]; det -= arr[0] * arr[5] * arr[8]; det -= arr[2] * arr[3] * arr[6]; det -= arr[1] * arr[4] * arr[7]; // Print the resultant matrix cout << "Required Matrix:\n"; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { cout << result[i][j] << " "; } cout << "\n"; } // Print the maximum determinant value cout << "Maximum determinant = " << det; } // Driver program int main() { int arr[] = {7, 4, 2, 5, 6, 3, 5, 1, 3}; findMaxDeterminant(arr); return 0; }
Output:
Required Matrix : 7 3 2 3 6 5 4 1 5 Maximum determinant = 148 Output: Required Matrix : 7 3 2 3 6 5 4 1 5 Maximum determinant = 148
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.