Find a Matrix of order 3 formed by given 9-elements whose determinant is maximum

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 }

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.