Ask Your Question

checking if a subset of columns of a matrix span a given vector

asked 2017-11-10 08:41:49 -0600

rivendell gravatar image

I'm new to Sage. I have a rectangular R*C matrix (R rows and C columns) and the rank of M is (possibly) smaller than both R and C. I want to check if a target vector T is in the span of a subset of columns of M. I have written the following code in Sage (I haven't included the whole code because the way I get M and T are rather cumbersome). I just want to check if the code does what I want.

Briefly, this is what my code is trying to do: M is my given matrix, I first check that T is indeed in the span of columns of M (the first if condition). If they do, I proceed to trim down M (which had C columns) to a matrix M1 which has exactly rank(M) many columns (this is what the first while loop does). After that, I keep removing the columns one by one to check if the rest of the columns contain T in their span (this is the second while loop). In the second while loop, I first remove a column from M2 (which is essentially a copy of M1) and call this matrix M3. To M3. I augment the vector T and check if the rank decreases. Since T was already in the span of M2, rank([M2 T]) should be the same as rank(M2). Now by removing column c and augmenting T to M2 doesn't decrease the rank, then I know that c is not necessary to generate T. This way I only keep those columns that are necessary to generate T.

It does return correct answers for the examples I tried, but I am going to run this code on a matrix with entries which vary a lot in magnitude (say the maximum is as large as 20^20 and minimum is 1)and typically the matrix dimensions could go up to 300. So planning to run it over a set of few hundred test cases over the weekend.

R = 155
C= 167
T = vector(QQ, R)
M1 = matrix(ZZ, R, C)

M1 = M
C1 = C
i2 = 0

if rank(M.augment(T)) == rank(M):
 print("The rank of M is")
 while i2 < C1 :
  if rank(M1.delete_columns([i2])) == rank(M1) :
   M1 = M1.delete_columns([i2])   
   C1 = C1 - 1
  else :
   i2 = i2+1

 C2 = M1.ncols()
 print("The number of columns in the trimmed down matrix M1 is")

 i3 = 0
 M2 = M1
 print("The rank of M1 which is now also the rank of M2 is")
 while i3 < C2 :
  M3 = M2.delete_columns([i3])
  if rank(M3.augment(T)) < rank(M2) :
   M2 = M3
   C2 = C2 - 1
  else :
   i3 = i3 + 1

print("Rank of matrix M is")
edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted

answered 2017-11-10 13:02:43 -0600

dan_fulea gravatar image

There are two distinct, non intersecting questions / issues in the post:

  • detect if two matrices have the same rank, the following is enough: print M.rank() == M.augment(T).rank()

  • detect generating columns for the vector space of the columns of the matrix M. Then print M.pivots() gives them.

edit flag offensive delete link more

answered 2017-11-10 09:54:01 -0600

tmonteil gravatar image

updated 2017-11-10 09:57:57 -0600

A vector V is in the span of the colomns of a matrix M if, and only if, the equation $MX=V$ has a solution. Here is an example:

sage: M = matrix([[1,2,3],[3,4,5],[5,6,7],[6,7,8]]) ; M
[1 2 3]
[3 4 5]
[5 6 7]
[6 7 8]

sage: V = vector([3,7,11,13])
sage: M.solve_right(V)
(1, 1, 0)

So in this case, V is the sum of the first and second column of M:

sage: M.column(0)+M.column(1) == V

You can see which columns contribute to the solution with:

 sage: M.solve_right(V).nonzero_positions()
 [0, 1]


sage: V = vector([1,2,3,4])
sage: M.solve_right(V)
ValueError: matrix equation has no solutions

So, in this case V is not in the span of the columns of M.

To deal with such exception, you can define:

sage: def is_in_span(M,V):
....:     try:
....:         M.solve_right(V)
....:         return True
....:     except ValueError:
....:         return False

You have:

sage: V = vector([3,7,11,13])
sage: is_in_span(M,V)
sage: V = vector([1,2,3,4])
sage: is_in_span(M,V)
edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools


Asked: 2017-11-10 08:41:49 -0600

Seen: 31 times

Last updated: Nov 10