How do I obtain all principal minors of a symmetric matrix without NumPy?

Question

I have a symmetric matrix:

[[a, b, c, d],
 [b, e, f, g],
 [c, f, h, i],
 [d, g, i, j]]

How do I generate all principal minors of this symmetric matrix without NumPy (out of interest)? I have a function that allows me to calculate the determinant of any square matrix, but I don't know how to generate the matrices for the minors.

I know that for a matrix of size 4, I must generate all principal minors of order 1, 2, 3, and 4. To generate all principal minors of order 1, I must remove both rows and columns 123, 124, 134, and 234. To generate all principal minors of order 2, I must remove both rows and columns 12, 13, 14, 23, 24, and 34. To generate all principal minors of order 3, I must remove both rows and columns 1, 2, 3, and 4. To generate all principal minors of order 4, I must remove no rows and columns. I understand this is related to "choosing" numbers (n!/((n-k)!k!)) and that I should pop these rows and individual items out of the nested list, but I am not sure how this all ties together.

Thanks in advance.

Here is what I have so far:

from itertools import combinations

def positive_semidefinite_test(A):
    MATRIX_DIMENSIONS = len(A)
    for i in range(MATRIX_DIMENSIONS):
        for combination in combinations(list(range(MATRIX_DIMENSIONS)), i):
          print(f"Combination: {combination}")
          B = A.copy()
          print(f"Original Matrix: {B}")
          for j in combination:
            for k in range(MATRIX_DIMENSIONS):
              B[k].pop(j)
            B.pop(j)
          print(f"Principal Minor: {B}")

If you run this code with a 4x4 matrix,

positive_semidefinite_test([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])

you would get the following output:

Combination: ()
Original Matrix: [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
Principal Minor: [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
Combination: (0,)
Original Matrix: [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
Principal Minor: [[6, 7, 8], [10, 11, 12], [14, 15, 16]]
Combination: (1,)
Original Matrix: [[2, 3, 4], [6, 7, 8], [10, 11, 12], [14, 15, 16]]
Principal Minor: [[2, 4], [10, 12], [14, 16]]
Combination: (2,)
Original Matrix: [[2, 4], [6, 8], [10, 12], [14, 16]]

For some reason the original matrix is not being copied properly even though I am making a new copy for each combination.

@mozway Out of interest. I've been doing this for a while now but I'm a little stuck. I'm ultimately trying to show that a given matrix is positive semidefinite using this. — , Dec 05 '21 at 06:16
You should probably provide your current code and the expected output ;) — mozway, Dec 05 '21 at 06:17
@mozway Added some code! I'm having trouble with filling the remove_index list so that I can remove the rows/columns from A using the sublists of remove_index to create matrices for principal minors. — , Dec 05 '21 at 07:46

score 0 · Accepted Answer · answered Dec 06 '21 at 01:54

Figured it out. Here's the code to generate all the matrices for all principal minors.

def positive_semidefinite_test(A):
    MATRIX_DIMENSIONS = len(A)
    for i in range(MATRIX_DIMENSIONS):
        for combination in combinations(list(range(MATRIX_DIMENSIONS)), i):
          B = [R[:] for R in A]
          for j in sorted(combination, reverse = True):
            for k in range(len(B)):
              del B[k][j]
            del B[j]
          print(B)

I replaced the pop() function with the del keyword (I don't need the returned value from pop()). Based on this response to a question about copying nested lists, apparently I need to copy each row of the nested list and then store it in a new list.

How do I obtain all principal minors of a symmetric matrix without NumPy?

1 Answers1