Assuming we have a square matrix M
, e.g.,
set.seed(1)
M <- matrix(rnorm(5*5), 5, 5)
> M
[,1] [,2] [,3] [,4] [,5]
[1,] -0.6264538 -0.8204684 1.5117812 -0.04493361 0.91897737
[2,] 0.1836433 0.4874291 0.3898432 -0.01619026 0.78213630
[3,] -0.8356286 0.7383247 -0.6212406 0.94383621 0.07456498
[4,] 1.5952808 0.5757814 -2.2146999 0.82122120 -1.98935170
[5,] 0.3295078 -0.3053884 1.1249309 0.59390132 0.61982575
I am wondering if there is an efficient way to find the a sub-matrix such that its determinant is the maximum among all the sub-matrices. The size of matrix should be larger than 1x1
but less than or equal to 5x5
. Some sub-matrix examples are like below
> M[c(1,5),c(2,3)]
[,1] [,2]
[1,] -0.8204684 1.511781
[2,] -0.3053884 1.124931
> M[c(1,2,4),c(1,4,5)]
[,1] [,2] [,3]
[1,] -0.6264538 -0.04493361 0.9189774
[2,] 0.1836433 -0.01619026 0.7821363
[3,] 1.5952808 0.82122120 -1.9893517
> M[1:4,2:5]
[,1] [,2] [,3] [,4]
[1,] -0.8204684 1.5117812 -0.04493361 0.91897737
[2,] 0.4874291 0.3898432 -0.01619026 0.78213630
[3,] 0.7383247 -0.6212406 0.94383621 0.07456498
[4,] 0.5757814 -2.2146999 0.82122120 -1.98935170
I can do it in a brute-force manner, i.e., iterating through all possible sub-matrices, but I believe there must be some optimization approach can take it easier.
I prefer to see solutions with CVXR
but not sure if this optimization problem can be formulated in a convex manner. Does anyone can help? Otherwise, other optimization packages are also welcome!
Since it has been four days without an answer I thought I would get the ball rolling with a working generalizable solution. Unfortunately, it falls into the brute force category, although for a 5 x 5 matrix it is fairly fast, completing in about 5ms:
The format of the output is:
The problem of course is that this doesn't scale well to larger matrices. Although it still works:
I'm getting over a second to find this solution for a 10 x 10 matrix.
I think this solution is O(n!) complexity, so you can forget about it for anything even a little larger than a 10 x 10 matrix. I have a feeling there should be an O(n³) solution, but my math isn't good enough to figure it out.
I guess that at least gives a benchmark for others to beat with more sophisticated methods...