extraction of principal submatrices

edit

The submatrix section of Wikipedia's matrix page mentions several possible definitions of principal submatrix of order k.

Given your question, you likely adopt the definition by which a principal submatrix of order k is a k by k submatrix in which the set of row indices that remain is the same as the set of column indices that remain.

So let us define principal_submatrix as a function that takes a matrix and a set of indices to keep.

def principal_submatrix(m, s, sort=False):
    """
    Return the submatrix of m corresponding to indices in s

    INPUT:

    - ``m`` -- a matrix

    - ``s`` -- an iterable for the indices of rows and columns to keep

    OUTPUT:

    The submatrix of ``m`` using the indices in ``s``.

    An optional argument specifies whether to sort the indices.
    Note that duplicate indices will be kept.
    """
    if sort:
        s = sorted(s)
    return m[s, s]

From there define principal_submatrices as a function that takes a matrix and the number of indices to keep.

def principal_submatrices(m, k):
    """
    Return the list of principal submatrices of m of order k

    These are the submatrices of m (assumed to be a square matrix)
    obtained by keeping k rows and columns, with the same indices.
    """
    S = Subsets(range(m.ncols()), k)
    return [principal_submatrix(m, s, sort=True) for s in S]

To illustrate these functions, let us use the following 4 by 4 matrix.

sage: m = matrix(ZZ, 4, range(4^2))
sage: m
[ 0  1  2  3]
[ 4  5  6  7]
[ 8  9 10 11]
[12 13 14 15]

Extract a specified principal submatrix:

sage: principal_submatrix(m, [0, 1, 3])
[ 0  1  3]
[ 4  5  7]
[12 13 15]

List all principal submatrices of each order:

sage: principal_submatrices(m, 0)
[[]]
sage: principal_submatrices(m, 1)
[[0], [5], [10], [15]]
sage: principal_submatrices(m, 2)
[
[0 1]  [ 0  2]  [ 0  3]  [ 5  6]  [ 5  7]  [10 11]
[4 5], [ 8 10], [12 15], [ 9 10], [13 15], [14 15]
]
sage: principal_submatrices(m, 3)
[
[ 0  1  2]  [ 0  1  3]  [ 0  2  3]  [ 5  6  7]
[ 4  5  6]  [ 4  5  7]  [ 8 10 11]  [ 9 10 11]
[ 8  9 10], [12 13 15], [12 14 15], [13 14 15]
]
sage: principal_submatrices(m, 4)
[
[ 0  1  2  3]
[ 4  5  6  7]
[ 8  9 10 11]
[12 13 14 15]
]