Ask Your Question
0

extraction of principal submatrices

asked 2017-11-18 06:15:01 -0600

anonymous user

Anonymous

How to extract all principal submatrices of fixed order say k from a given square matrix of order n by n. please explain with one example

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2017-11-18 10:20:29 -0600

updated 2017-11-18 11:31:37 -0600

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]
]
edit flag offensive delete link more

Comments

Thank you.

A gravatar imageA ( 2017-11-18 23:41:20 -0600 )edit

If this answers your question, you can click the tick sign next to the answer; this will mark this answer as solving your question, and mark your question as solved.

slelievre gravatar imageslelievre ( 2017-11-21 11:30:58 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-11-18 06:15:01 -0600

Seen: 32 times

Last updated: Nov 18