Calculate Rank and Nullspace of a Matrix

Calculate Rank and Nullspace of a Matrix Calculate Rank and Nullspace of a Matrix Theory

Consider a matrix A with rank k, conduct SVD to the matrix:
A = U S V T A = USV^T A=USVT
Column space: the first k k k left singular vectors, the column of U: { u 1 , u 2 , . . , u k } {u_1,u_2,..,u_k} {u1​,u2​,..,uk​} provide an orthonormal basis of the column space of A A A.

Row space: the first k k k left singular vectors, the column of V: { v 1 , v 2 , . . , v k } {v_1,v_2,..,v_k} {v1​,v2​,..,vk​} provide an orthonormal basis of the row space of last A A A.

Null space: The last right singular vectors,: { v k + 1 , v k + 2 , . . , v n } {v_{k+1},v_{k+2},..,v_n} {vk+1​,vk+2​,..,vn​} span the nullspace of matrix A A A.

Proof

Suppose a vector x → overrightarrow{x} x can be expressed as a linear combination of the last n − k n-k n−k columns of V with some real-valued weights w i w_i wi​.
x → = ∑ i = k + 1 n w i v i → overrightarrow{x} = sum_{i = k+1}^n w_i overrightarrow{v_i} x =i=k+1∑n​wi​vi​ ​
Then A x → Aoverrightarrow{x} Ax can be expressed as:
A x → = A ( ∑ i = k + 1 n w i v i → ) = ∑ i = k + 1 n w i ( A v i → ) Aoverrightarrow{x} = A(sum_{i = k+1}^n w_i overrightarrow{v_i}) = sum_{i = k+1}^n w_i (A overrightarrow{v_i}) Ax =A(i=k+1∑n​wi​vi​ ​)=i=k+1∑n​wi​(Avi​ ​)
Any one of the terms in the sum :
∑ i = k + 1 n A v i → = ( U Σ V T ) v i → = U Σ ( V T v i → ) = U Σ e i → sum_{i = k+1}^n A overrightarrow{v_i} = (U Sigma V^T) overrightarrow{v_i} = U Sigma (V^T overrightarrow{v_i} ) = USigma overrightarrow{e_i} i=k+1∑n​Avi​ ​=(UΣVT)vi​ ​=UΣ(VTvi​ ​)=UΣei​ ​
Since vectors in V T V^T VT is orthonormal, e i → overrightarrow{e_i} ei​ ​ is a basis that e i → = { 00...1...0 } overrightarrow{e_i} = {0 0 ... 1 ...0} ei​ ​={00...1...0} with “1” in the i’th row.
Now, because i in the sum only ranged over k+1 to n, then when multiply e i → overrightarrow{e_i} ei​ ​ by Σ Sigma Σ, which only has non-zeros along the diagonal up to first k columns, we have
U Σ e i → = 0 U Sigma overrightarrow{e_i} = 0 UΣei​ ​=0
hence prove that
A x → = 0 Aoverrightarrow{x}=0 Ax =0 for any vector x → overrightarrow{x} x that lives in the subspace spanned by the last n − k n-k n−k columns of V i.e. it lies in the subspace.

Code

Code 源代码在这个网站

https://scipy-cookbook.readthedocs.io/items/RankNullspace.html

这个网站还挺有意思的写了很多实用的python工具以后有机会探索一下

#!python
import numpy as np
from numpy.linalg import svd


def rank(A, atol=1e-13, rtol=0):
    A = np.atleast_2d(A)
    s = svd(A, compute_uv=False)
    tol = max(atol, rtol * s[0])
    rank = int((s >= tol).sum())
    return rank


def nullspace(A, atol=1e-13, rtol=0):
    A = np.atleast_2d(A)
    u, s, vh = svd(A)
    tol = max(atol, rtol * s[0])
    nnz = (s >= tol).sum()
    ns = vh[nnz:].conj().T
    return ns

Demo:

import numpy as np

from rank_nullspace import rank, nullspace


def checkit(a):
    print "a:"
    print a
    r = rank(a)
    print "rank is", r
    ns = nullspace(a)
    print "nullspace:"
    print ns
    if ns.size > 0:
        res = np.abs(np.dot(a, ns)).max()
        print "max residual is", res


print "-"*25

a = np.array([[1.0, 2.0, 3.0], [4.0, 5.0, 6.0], [7.0, 8.0, 9.0]])
checkit(a)

print "-"*25

a = np.array([[0.0, 2.0, 3.0], [4.0, 5.0, 6.0], [7.0, 8.0, 9.0]])
checkit(a)

print "-"*25

a = np.array([[0.0, 1.0, 2.0, 4.0], [1.0, 2.0, 3.0, 4.0]])
checkit(a)

print "-"*25

a = np.array([[1.0,   1.0j,   2.0+2.0j],
              [1.0j, -1.0,   -2.0+2.0j],
              [0.5,   0.5j,   1.0+1.0j]])
checkit(a)

print "-"*25

The output is supposed to be:

-------------------------
a:
[[ 1.  2.  3.]
 [ 4.  5.  6.]
 [ 7.  8.  9.]]
rank is 2
nullspace:
[[-0.40824829]
 [ 0.81649658]
 [-0.40824829]]
max residual is 4.4408920985e-16
-------------------------
a:
[[ 0.  2.  3.]
 [ 4.  5.  6.]
 [ 7.  8.  9.]]
rank is 3
nullspace:
[]
-------------------------
a:
[[ 0.  1.  2.  4.]
 [ 1.  2.  3.  4.]]
rank is 2
nullspace:
[[-0.48666474 -0.61177492]
 [-0.27946883  0.76717915]
 [ 0.76613356 -0.15540423]
 [-0.31319957 -0.11409267]]
max residual is 3.88578058619e-16
-------------------------
a:
[[ 1.0+0.j   0.0+1.j   2.0+2.j ]
 [ 0.0+1.j  -1.0+0.j  -2.0+2.j ]
 [ 0.5+0.j   0.0+0.5j  1.0+1.j ]]
rank is 1
nullspace:
[[ 0.00000000-0.j         -0.94868330-0.j        ]
 [ 0.13333333+0.93333333j  0.00000000-0.10540926j]
 [ 0.20000000-0.26666667j  0.21081851-0.21081851j]]
max residual is 1.04295984227e-15
-------------------------