def complete_matrix(matrix):
    """
    Completes a matrix in RREF form of size N x N-1 (that is, it contains N-1 bit strings
    that are N bits long) by finding the missing row and adding a linearly independent
    string in its position.

    Parameters:
        matrix (list[list[bool]]): The matrix to complete. It must be in RREF form already,
            and be size N x N-1.

    Returns:
        The solution vector (AKA the right-hand-side vector) for the equations
        represented by the matrix. This is what the matrix must be evaluated against during
        back substitution (because it's not going to be all 0s after this step).

    Remarks:
        The algorithm here is described in section 18.13.2 (Completing the Basis with an
        nth Vector Not Orthogonal to a) of the Loceff document:
        http://lapastillaroja.net/wp-content/uploads/2016/09/Intro_to_QC_Vol_1_Loceff.pdf
        
        You should really go look at that to understand what's going on here. It's hard
        to describe it all in the code, but basically the matrix is N by N-1 right now
        and this will find the missing row and insert a valid, linearly independent string
        at its location.
    """

    # This is the index of the row that is missing. It defaults to the row past the
    # bottom of the matrix, because if the entire walk doesn't find a missing
    # row, that means the missing one comes after everything that's already in
    # there.
    missing_row_index = len(matrix)

    for i in range(0, len(matrix)):
        current_row = matrix[i]
        if not current_row[i]:
            # Check if this row has a 0 in the diagonal position. If it
            # does, the missing row that we need to add goes here.
            missing_row_index = i
            break

    # Create the missing row, with a 1 in the diagonal position
    missing_row = [False] * len(matrix[0])
    missing_row[missing_row_index] = True

    # Insert the row into the missing index. Note that this handles all
    # three cases described in the paper. Row = 0 means all diagonals are
    # 0 so this gets added to the top, row = N means all diagonals are 1
    # so this gets added to the bottom, row = anything else means it
    # gets put into that particular index.
    matrix.insert(missing_row_index, missing_row)

    # Now we need to return the vector that represents the right-hand side of the
    # equations being solved for with the matrix. If the matrix represents the
    # problem (M · S) % 2 = 0 (where M is the matrix and S is the secret string
    # hidden in the function being evaluated), this represents that 0 on the
    # right-hand side of the equation. For the missing string we just added to
    # be truly independent, the equation for it has to equal 1 instead of 0 at the
    # row position where we just added the missing string.
    # Conveniently enough, that ends up being exactly the same thing as the string
    # itself, so we can just return the missing string as the solution vector.
    return missing_row