Skip to main content

How to use gurobi to describe the process of finding the rank of matrix?

Answered

Comments

6 comments

  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Wenny,

    Consider a matrix M with \( p \) rows.  If the matrix has rank \( n \) then its columns span a space of dimension \( n \) where \( n \leq p \).  If \( n < p \) then there exists a standard basis vector, \( e_i \in \mathbf{R}^p \) for some \( i \in \{1, \ldots, p\} \) such that \( e_i \) is not in the column span.  We can add \( e_i \) to the collection of column vectors to increase the dimension spanned by 1.

    Now a set of vectors span \( \mathbf{R}^p \) if and only if each standard basis vector \( e_i \) is in the span of the vectors.  So the approach to calculate the matrix rank will be to borrow standard basis vectors to add to our column vector span to ensure that we span \( \mathbf{R}^p \) - but borrowing as few standard basis vectors as possible, with the number borrowed equal to \( p - rank(M) \).

    m = gp.Model()

    p,q = 3,3 # as an example, overwritten for testing

    # uncomment the following 3 lines for testing
    #A = np.array([[0,1,0], [0,1,0],[0,2,0],[1,0,0]])
    #p=A.shape[0]
    #q=A.shape[1]

    # the matrix (size = (p,q)) of variables whose rank we want to calculate
    M = m.addMVar((p,q), lb=-float("inf"), name="M")

    #scalars[i,j] is the scalar for the i-th column of M in linear combination for e_j
    scalars = m.addMVar((q,p), lb=-float("inf"), name="scalars")

    #e_scalars[i,j] is the scalar for e_i in linear combination for e_j
    e_scalars = m.addMVar((p,p), lb=-float("inf"), name="scalars")

    #e_borrowed[i] == 1 if e_i is "borrowed" to use in creating full dimensional span
    e_borrowed = m.addMVar(p, vtype="B")

    #each e_i must be in the span of column vectors + span of "borrowed" basis vectors
    m.addConstr(M@scalars + e_scalars == np.eye(p))

    # if e_[i] is not borrowed then we cannot use it in linear combinations
    m.addConstr((e_borrowed == 0) >> (e_scalars.transpose()==0))

    #minimize the number of borrowed basis vectors
    m.setObjective(e_borrowed.sum(), gp.GRB.MINIMIZE)

    # uncomment the following line for testing
    #m.addConstr(M == A)

    m.optimize()

    rank = p - round(m.ObjVal)

    # uncomment the following line for testing
    #print("Passed test:", np.linalg.matrix_rank(A) == rank)

    Because the objective function is needed to calculate the rank you will need to be careful if embedding this in a larger model - i.e. take care so that the other constraints, and any addition to the objective don't disturb the downwards pressure on the e_borrowed variables.

    - Riley

    1
  • wenny li
    Gurobi-versary
    Conversationalist
    First Question

    Actually,this line always have an error 

    m.addConstr((e_borrowed == 0) >> (e_scalars.transpose()==0))

    File "src\gurobipy\model.pxi", line 3623, in gurobipy.Model.addConstr
      File "src\gurobipy\mlinexpr.pxi", line 706, in gurobipy.MLinExpr.item
      File "src\gurobipy\mlinexpr.pxi", line 708, in gurobipy.MLinExpr.item
    ValueError: can only convert an array of size 1 to a Python scalar

    I can't find the problem.I really need your help,thank you so much!

    0
  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Wenny,

    Apologies, the above code only works with Gurobi 11+.  Are you able to upgrade?

    Or alternatively replace the line that doesn't work with the following, in order to use an earlier version of Gurobi:

    for i in range(p):
        for j in range(p):
            m.addConstr((e_borrowed[i] == 0) >> (e_scalars[i,j]==0))

    - Riley

     

    1
  • wenny li
    Gurobi-versary
    Conversationalist
    First Question

    Thanks for your reply!I upgrade Gurobi and get the right result.

    0
  • wenny li
    Gurobi-versary
    Conversationalist
    First Question

    Hi Riley,

    I'm sorry to ask you again.Like you mentioned above,when I embedding this code in a larger model,I need  add other object.But this affects the minimization of e_borrowed,so I wonder if there is a solution that doesn't use objective function.For example, whether can use gurobi to simulate the process of matrix simplification, and then calculate the number of non-zero rows to represent the rank.

    One additional condition that might simplify the problem,that is my matrix contains only 0-1 variables

    0
  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Wenny,

    I wonder if there is a solution that doesn't use objective function

    There may be, but I have my doubts, and in any case I cannot think of one unfortunately.

    - Riley

    0

Please sign in to leave a comment.