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())
