def dot_prod_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]
    return Mat(
        (A.D[0], B.D[1]),
        {
            (row, col): matutil.mat2rowdict(A)[row] * matutil.mat2coldict(B)[col]
            for row in matutil.mat2rowdict(A)
            for col in matutil.mat2coldict(B)
        },
    )

def find_error_matrix(S):
    """
    Input: a matrix S whose columns are error syndromes
    Output: a matrix whose cth column is the error corresponding to the cth column of S.
    Example:
        >>> S = listlist2mat([[0,one,one,one],[0,one,0,0],[0,0,0,one]])
        >>> find_error_matrix(S)
        Mat(({0, 1, 2, 3, 4, 5, 6}, {0, 1, 2, 3}), {(1, 2): 0, (3, 2): one, (0, 0): 0, (4, 3): one, (3, 0): 0, (6, 0): 0, (2, 1): 0, (6, 2): 0, (2, 3): 0, (5, 1): one, (4, 2): 0, (1, 0): 0, (0, 3): 0, (4, 0): 0, (0, 1): 0, (3, 3): 0, (4, 1): 0, (6, 1): 0, (3, 1): 0, (1, 1): 0, (6, 3): 0, (2, 0): 0, (5, 0): 0, (2, 2): 0, (1, 3): 0, (5, 3): 0, (5, 2): 0, (0, 2): 0})
    """
    return coldict2mat([find_error(mat2coldict(S)[k]) for k in mat2coldict(S)])

def is_invertible(M):
    '''
input: A matrix, M
outpit: A boolean indicating if M is invertible.
>>> M = Mat(({0, 1, 2, 3}, {0, 1, 2, 3}), {(0, 1): 0, (1, 2): 1, (3, 2): 0, (0, 0): 1, (3, 3): 4, (3, 0): 0, (3, 1): 0, (1, 1): 2, (2, 1): 0, (0, 2): 1, (2, 0): 0, (1, 3): 0, (2, 3): 1, (2, 2): 3, (1, 0): 0, (0, 3): 0})
>>> is_invertible(M)
True
'''
    if M.D[0] != M.D[1]: return False
    if (len(list(mat2coldict(M).values())) == rank(list(mat2coldict(M).values()))):
        return True
    else: return False

def Mv_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]
    cols = mat2coldict(B)
    rcols = {}
    for index, col in cols.items():
        rcols[index] = A * col
    return coldict2mat(rcols)

def dot_product_vec_mat_mult(v, M):
    assert v.D == M.D[0]
    result = Vec(M.D[1], {r: 0 for r in M.D[1]})
    cols = mat2coldict(M)
    for k in M.D[1]:
        result.f[k] = v * cols[k]
    return result

def lin_comb_mat_vec_mult(M, v):
    assert M.D[1] == v.D
    result = Vec(M.D[0], {c: 0 for c in M.D[0]})
    cols = mat2coldict(M)
    for k, value in v.f.items():
        result = result + value * (cols[k])
    return result

def dot_product_vec_mat_mult(v, M):
    assert(v.D == M.D[0])
    res = Vec(M.D[1], {})
    dct = matutil.mat2coldict(M)
    for k,n in dct.items():
        res[k] = n * v
    return res

def lin_comb_mat_vec_mult(M, v):
    assert(M.D[1] == v.D)
    res = Vec(M.D[0], {})
    dct = matutil.mat2coldict(M)
    for k in v.D:
        res = res + v[k]*dct[k]
    return res

def lin_comb_mat_vec_mult(M, v):
    assert M.D[1] == v.D
    from matutil import mat2coldict

    m = mat2coldict(M)
    y = sum([v[c] * m[c] for c in m.D[1]])
    return y

def is_invertible(M): 
    '''
    input: A matrix, M
    outpit: A boolean indicating if M is invertible.
    
    >>> M = Mat(({0, 1, 2, 3}, {0, 1, 2, 3}), {(0, 1): 0, (1, 2): 1, (3, 2): 0, (0, 0): 1, (3, 3): 4, (3, 0): 0, (3, 1): 0, (1, 1): 2, (2, 1): 0, (0, 2): 1, (2, 0): 0, (1, 3): 0, (2, 3): 1, (2, 2): 3, (1, 0): 0, (0, 3): 0})
    >>> is_invertible(M)
    True
    '''
    nullspace = solve(M, list2vec([0]))
    ker_zero = nullspace == Vec(nullspace.D, {})

    im_f_eq_codomain = independence.rank(subset_basis(matutil.mat2coldict(M).values())) == len(M.D[1])

    # invertible if its one-to-one, onto, and square matrix
    return ker_zero and im_f_eq_codomain and len(matutil.mat2coldict(M)) == len(matutil.mat2rowdict(M))

def dot_prod_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]
    import vec, matutil
    A_dict = matutil.mat2rowdict(A)
    B_dict = matutil.mat2coldict(B)
    dp = {(i,j): A_dict[i]*B_dict[j] for j in B_dict.keys() for i in A_dict.keys()}
    return Mat((set(A_dict.keys()), set(B_dict.keys())), dp)

def lin_comb_mat_vec_mult(M, v):
    assert M.D[1] == v.D
    import matutil
    from matutil import mat2coldict

    mat2col = mat2coldict(M)
    return sum([getitem(v, key) * mat2col[key] for key in v.D])

def Mv_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]
#    print (str(A.D) + str(A.f))
#    print (str(B.D) + str(B.f))
#    print('\n')
    colsB = utils.mat2coldict(B)
    return utils.coldict2mat({k:A*colsB[k] for k in colsB})

def lin_comb_mat_vec_mult(M, v):
    assert(M.D[1] == v.D)


    # vec_list = []
    #
    #
    # col_dict = matutil.mat2coldict(M)
    # for key, val in col_dict.items():
    #     vec_list.append(mult_vec_by_int(val, v[key]))
    #
    # new_v = Vec(M.D[0], {})
    #
    # for vec in vec_list:
    #     new_v += vec
    #
    # return new_v

    new_v = Vec(M.D[0], {})

    col_dict = matutil.mat2coldict(M)

    for key, val in col_dict.items():
        new_v += v[key] * val

    return new_v

def mat_move2board(Y):
    '''
    Input:
        - Y: a Mat each column of which is a {'y1', 'y2', 'y3'}-Vec
          giving the whiteboard coordinates of a point q.
    Output:
        - a Mat each column of which is the corresponding point in the
          whiteboard plane (the point of intersection with the whiteboard plane 
          of the line through the origin and q).

    Example:
    >>> Y_in = Mat(({'y1', 'y2', 'y3'}, {0,1,2,3}),
         {('y1',0):2, ('y2',0):4, ('y3',0):8,
          ('y1',1):10, ('y2',1):5, ('y3',1):5,
          ('y1',2):4, ('y2',2):25, ('y3',2):2,
          ('y1',3):5, ('y2',3):10, ('y3',3):4})
    >>> print(Y_in)
    
            0  1  2  3
          ------------
     y1  |  2 10  4  5
     y2  |  4  5 25 10
     y3  |  8  5  2  4
    
    >>> print(mat_move2board(Y_in))
    
               0 1    2    3
          ------------------
     y1  |  0.25 2    2 1.25
     y2  |   0.5 1 12.5  2.5
     y3  |     1 1    1    1
    '''
    y_in = mat2coldict(Y)
    y_out = {x:move2board(y_in[x]) for x in y_in.keys()}
    return coldict2mat(y_out)

def mat_move2board(Y):
    '''
    Input:
        - Y: a Mat each column of which is a {'y1', 'y2', 'y3'}-Vec
          giving the whiteboard coordinates of a point q.
    Output:
        - a Mat each column of which is the corresponding point in the
          whiteboard plane (the point of intersection with the whiteboard plane 
          of the line through the origin and q).

    Example:
    >>> Y_in = Mat(({'y1', 'y2', 'y3'}, {0,1,2,3}),
    ...     {('y1',0):2, ('y2',0):4, ('y3',0):8,
    ...      ('y1',1):10, ('y2',1):5, ('y3',1):5,
    ...      ('y1',2):4, ('y2',2):25, ('y3',2):2,
    ...      ('y1',3):5, ('y2',3):10, ('y3',3):4})
    >>> print(Y_in)
    <BLANKLINE>
            0  1  2  3
          ------------
     y1  |  2 10  4  5
     y2  |  4  5 25 10
     y3  |  8  5  2  4
    <BLANKLINE>
    >>> print(mat_move2board(Y_in))
    <BLANKLINE>
               0 1    2    3
          ------------------
     y1  |  0.25 2    2 1.25
     y2  |   0.5 1 12.5  2.5
     y3  |     1 1    1    1
    <BLANKLINE>
    '''
    coldict = mat2coldict(Y)
    return coldict2mat({key:move2board(val) for key, val in coldict.items()})

def is_invertible(M): 
    '''
    input: A matrix, M
    outpit: A boolean indicating if M is invertible.
    
    >>> M = Mat(({0, 1, 2, 3}, {0, 1, 2, 3}), {(0, 1): 0, (1, 2): 1,
    (3, 2): 0, (0, 0): 1, (3, 3): 4, (3, 0): 0, (3, 1): 0, (1, 1): 2,
    (2, 1): 0, (0, 2): 1, (2, 0): 0, (1, 3): 0, (2, 3): 1, (2, 2): 3,
    (1, 0): 0, (0, 3): 0})
    >>> is_invertible(M)
    True
    '''
    R=[]
    C=[]
    R_dict = mat2rowdict(M)
    C_dict = mat2coldict(M)
    for k,v in R_dict.items():
        R.append(v)
    for k,v in C_dict.items():
        C.append(v)
        
    if rank(R) != rank(C):
        return False
    elif my_is_independent(R) == False:
        return False
    elif my_is_independent(C) == False:
        return False
    return True

def lin_comb_mat_vec_mult(M, v):
    assert(M.D[1] == v.D)
    cols = mat2coldict(M)
    new_dict= Vec(M.D[0],{})
    for k,col_vec in cols.items():
        tmp = v[k] * col_vec
        new_dict = new_dict + tmp
    return new_dict

def Mv_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]
    from matutil import mat2coldict
    from matutil import coldict2mat
    columns = mat2coldict(B)
    for column,colVec in columns.items():
    	columns[column] = A*colVec
    return coldict2mat(columns)

def Mv_mat_mat_mult(A, B):
    assert A.D[1] == B.D[0]
    dct = matutil.mat2coldict(B)
    #return (matutil.coldict2mat(dict([ (c , lin_comb_mat_vec_mult(A, dct[c]))  for c in dct])))
    v = Vec(dct.keys(), dict())
    for c in dct:
        print(A * dct[c])
        v[c] = A * dct[c]