Ask Your Question
2

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")
 print(rank(M))
 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")
 print(C2)


 i3 = 0
 M2 = M1
 print("The rank of M1 which is now also the rank of M2 is")
 print(rank(M2))
 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")
print(M.rank())
edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
0

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
True

You can see which columns contribute to the solution with:

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

However:

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)
True
sage: V = vector([1,2,3,4])
sage: is_in_span(M,V)
False
edit flag offensive delete link more
0

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

Your Answer

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

Add Answer

Question Tools

Stats

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

Seen: 429 times

Last updated: Nov 10 '17