Feature: Compute the spark of a matrix

Define a function and associated unit tests to compute the spark of a matrix.

Note that the spark is NP-hard to compute in general. Here is a candidate function for computing the spark of a matrix:

def spark(matrix: np.ndarray) -> int:
    """Compute the spark of the given matrix."""

    # The spark of a matrix is equal to 1 if and only if the matrix has a zero column.
    if np.any(np.sum(matrix, axis=0) == 0):
        return 1

    # Otherwise, compute the NP-hard spark computation.
    _, n = matrix.shape
    for k in range(1, n + 1):
        for cols in combinations(range(n), k):
            submatrix = matrix[:, cols]
            if is_linearly_dependent(submatrix):
                return k
    # If no dependent set is found, return n + 1
    return n + 1

We would also need unit tests as well. Something like the following, for example:

@pytest.mark.parametrize("matrix, expected_result", [
    # Spark is 3 since (no set of 1 or 2 columns that are linearly dependnet)
    # But there is a set of 3 columns that are linearly dependnet.
    (
        np.array([
            [1, 2, 0, 1],
            [1, 2, 0, 2],
            [1, 2, 0, 3],
            [1, 0, -3, 4],
        ]),
        3
    ),
    # Spark of matrix is 1 if there is a column of all zeros.
    (
        np.array([
            [1, 2, 0, 0],
            [1, 2, 0, 0],
            [1, 2, 0, 0],
            [1, 0, -3, 0],
        ]),
        1
    )
])
def test_spark(matrix, expected_result):
    np.testing.assert_allclose(spark(matrix), expected_result)

Presumably, this function would belong in matrix_props/ and would require a more appropriate and thoroughly written docstring.

vprusso / toqito

Feature: Compute the spark of a matrix #620