def solve_matrix(matrix, right_hand_side):
    """
    Performs back substitution on an N x N boolean matrix in RREF form to determine the
    solution to each equation represented by its rows (noting that the equations are
    of the form [X · S] % 2 = 0). For Simon's Algorithm, this gives you the secret
    string S that's hidden in the original function being evaluated.

    Parameters:
        matrix (list[list[bool]]): The matrix representing the equations to solve. It must be
            N x N and already in RREF form.
        right_hand_side (list[bool]): A vector representing the right-hand-side of the
            equations held in the matrix. These are the "solutions" to each equation.

    Returns:
        The solution to the matrix, in this case the secret string S.

    Remarks:
        For a good, visual example of how this process works, take a look at this math
        StackExchange post:
        https://math.stackexchange.com/a/45348
    """

    secret_string = [False] * len(matrix)

    # Start at the bottom row and work our way up to the top
    for row_index in range(len(matrix) - 1, -1, -1):
        row = matrix[row_index]
        right_hand_side_value = right_hand_side[row_index]  # Solution for this equation

        # Walk through the values of the row (these correspond to the variables for each
        # row beneath it, which have already been solved at this point since we're going
        # bottom up); if this row has a 1 for that variable, XOR the solution value with
        # whatever that row's value ended up being.
        for column_index in range(row_index + 1, len(row)):
            if row[column_index]:
                right_hand_side_value ^= secret_string[column_index]

        # Once the terms have been calculated, assign the solution value at this row's
        # index to the result of the equation.
        secret_string[row_index] = right_hand_side_value

    return secret_string