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

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 close merge delete

Sort by » oldest newest most voted

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

more

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.

more