Inverse of a matrix after a row-and-column removal

Input: M or M_inverse Output: Inverse Remove row-col, calculate inverse Manipulate M_inverse, remove row-col

Is using the matrix inverse faster than calculating the inverse of the smaller matrix?

This is a generalization and a detailed explanation of a neat little trick I came across in the paper Optimal Brain Compression. The solution uses the same approach as this answer but also extends it to a more general case. A Python implementation is also provided for both the cases.

The Original Problem

You are given an invertible n-by-n matrix and its inverse . Now let's say the i-th row and i-th column of the matrix are removed. Let's call this matrix . We would like to calculate the inverse of this matrix efficiently.

import numpy as np

def remove_row(matrix: np.matrix, index: int):
return np.delete(matrix, index, axis=0)

def remove_column(matrix: np.matrix, index: int):
    return np.delete(matrix, index, axis=1)

def remove_row_and_column(matrix: np.matrix, row_index: int, col_index: int):
    return remove_column(remove_row(matrix, row_index), col_index)
    
matrix = np.random.randn(5,5)
matrix_inverse = np.linalg.inv(matrix)

index = 3
smaller_matrix = remove_row_and_column(matrix, index, index)

If you do not care about efficiency, the problem is trivial - you simply calculate the inverse of . But because we also know , can we somehow make use of it? In other words, can we somehow manipulate to calculate the inverse of , and if so, is it more efficient (or faster) compared to the trivial method?

# a solution that is easy to come up with implement but inefficient:
smaller_matrix_inverse = np.linalg.inv(smaller_matrix)

def computer_smaller_matrix_inverse_efficiently(matrix_inverse, index):
    # can we only use "matrix_inverse" alongwith the index of the row and column removed
    # to calculate the inverse of the smaller matrix?
    ...

A more general problem

We can extend this idea to a case where the indices of the removed row and column are different - if the i-th row and j-th column of the matrix are removed, can we calculate the inverse of this (n-1)x(n-1) matrix by directly manipulating ? We will explore this idea in a bit.

row_index = 3
col_index = 1
smaller_matrix = remove_row_and_column(matrix, row_index, col_index)

def computer_smaller_matrix_inverse_efficiently(matrix_inverse, row_index, col_index):
    # can we only use "matrix_inverse" alongwith the indices of the row and column removed
    # to calculate the inverse of the smaller matrix?
    ...

The Solution

Solving a specific problem first

Consider the case in which the last row and last column are removed. In other words, we want to calculate the inverse of . Note that it is a (n-1)x(n-1) matrix. We can write it in block matrix form as:

Note that:

  • is a (n-1)x(n-1) matrix.
  • is a (n-1)x1 matrix (aka a column vector).
  • is a 1x(n-1) matrix (aka a row vector).
  • is a 1x1 matrix (aka a scalar).

Similarly, we can write in the block matrix form as:

Note that:

  • is a (n-1)x(n-1) matrix.
  • is a (n-1)x1 matrix (aka a column vector).
  • is a 1x(n-1) matrix (aka a row vector).
  • is a 1x1 matrix (aka a scalar).

Also note that is actually equal to . We would like to find by manipulating .

Now let's do some elementary algebra:

Note that:

  • are (n-1)x(n-1) matrices.
  • are (n-1)x1 matrices (aka column vectors).

Now let's denote the i-th column of the matrix as and j-th row of the matrix as . Then notice that is actually equal to with the last element missing. Similarly is actually equal to with the last element missing. Then we make the following series of observations:

  • is actually equal to the matrix with the last column and row missing.
  • In other words, .
  • Similarly is the same as with the last row and column missing:
  • Finally we can write:

In simple words, the inverse of a matrix with the last row and column removed is equal to the inverse of minus the product of last column and last row divided by the last diagonal value of .

Is it faster than just calculating the inverse again?

Well of course it is! Note that we already had access to . All we had to calculate was the product of the n-dimensional column vector with a n-dimensional row vector. Calculating this product has a complexity of . Calculating the inverse of a matrix has complexity .

Solving the original problem

We want to calculate the inverse of for any i. We just solved the problem when . To solve for any i, we will deploy the following strategy:

  • Swap the i-th and n-th columns. Similarly swap the i-th and n-th rows. Let's call this matrix . This can be done using a permutation matrix . Note that is obtained by swapping the i-th and n-th columns of . Thus is symmetric.

  • It is easy to calculate from using the identity .

  • Calculate the inverse of by using only. We know how to do this by now.

  • Interpret the manipulation of in terms of since we know how they are connected:

  • This gives us the answer:

  • Here is the i-th value of the diagonal of .
def calculate_smaller_matrix_inverse(matrix_inverse: np.matrix, index: int):
    '''
    a faster way to solve
    np.linalg.inv( remove_row_and_column(matrix, index, index) )
    '''
    to_subtract = matrix_inverse[:, index].reshape(-1,1) @ matrix_inverse[index, :].reshape(1,-1)
    to_subtract /= matrix_inverse[index, index]
    result = matrix_inverse - to_subtract
    return remove_row_and_column(result, index, index)

Solution to a more general problem

Now that we know how to calculate , we can use the same approach to calculate the inverse of a matrix whose i-th row and j-th column have been removed. We use the notation to denote the matrix with i-th row and j-th column removed.

  • Use a permutation matrix to swap rows i and n. Call this row permutation matrix . Similarly use another permutation matrix to swap columns j and n. Call this column permutation matrix .

  • Note that this gives us . Next we establish the relationship between the inverse matrices .

  • The inverse of is equal to the inverse of . We know how to use to get to :

  • Interpret the manipulation of in terms of since we know how they are connected:

In other words, removal of the last row and column of is equivalent to removal of j-th row and i-th column of .

Similarly, the last column of is the same as the i-th column of and the last row of is the same as the j-th row of . Using similar logic, we can see that:

Thus the final solution is given as:

def calculate_smaller_matrix_inverse(matrix_inverse: np.matrix, row_index: int, col_index: int):
    '''
    a faster way to solve:
    np.linalg.inv( remove_row_and_column(matrix, row_index, col_index) )
    '''
    to_subtract = matrix_inverse[:, row_index].reshape(-1,1) @ matrix_inverse[col_index, :].reshape(1,-1)
    to_subtract /= matrix_inverse[col_index, row_index]
    result = matrix_inverse - to_subtract
    return remove_row_and_column(result, col_index, row_index)

Related articles: