Skip to content

positive_semidefinite_rank

Calculates the positive semidefinite rank of a nonnegative matrix.

positive_semidefinite_rank 

positive_semidefinite_rank(
    mat: ndarray, max_rank: int = 10
) -> int | None

Compute the positive semidefinite rank (PSD rank) of a nonnegative matrix.

The definition of PSD rank is defined in 1. Finds the PSD rank of an input matrix by checking feasibility for increasing rank.

Parameters:

  • mat (ndarray) –

    Matrix of interest.

  • max_rank (int, default: 10 ) –

    The maximum rank to check (default is 10).

Returns:

  • int | None –

    The positive semidefinite rank if found within max_rank, or None otherwise.

Examples:

As an example (Equation 21 from 2), the PSD rank of the following matrix

\[ A = \frac{1}{2} \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} \]

is known to be \(\text{rank}_{\text{PSD}}(A) = 2\).

import numpy as np
from toqito.matrix_props import positive_semidefinite_rank

A = 1/2 * np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]])
print(positive_semidefinite_rank(A))

2

The PSD rank of the identity matrix is the dimension of the matrix 1.

import numpy as np
from toqito.matrix_props import positive_semidefinite_rank

print(positive_semidefinite_rank(np.identity(3)))

3

References

1 Fawzi, Hamza and Gouveia, Jo{\~a}o and Parrilo, Pablo and Robinson, Richard and Thomas, Rekha. Positive semidefinite rank. Mathematical Programming. vol. 153. (2015). link.
2 Heinosaari, Teiko and Hillery, Mark. Can a qudit carry more information than a dit?. arXiv preprint arXiv:2406.16566. (2024). link.

Source code in toqito/matrix_props/positive_semidefinite_rank.py 
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def positive_semidefinite_rank(mat: np.ndarray, max_rank: int = 10) -> int | None:
    r"""Compute the positive semidefinite rank (PSD rank) of a nonnegative matrix.

    The definition of PSD rank is defined in [@fawzi2015positive].
    Finds the PSD rank of an input matrix by checking feasibility for increasing rank.

    Args:
        mat: Matrix of interest.
        max_rank: The maximum rank to check (default is 10).

    Returns:
        The positive semidefinite rank if found within `max_rank`, or `None` otherwise.

    Examples:
        As an example (Equation 21 from [@heinosaari2024can]), the PSD rank of the following matrix

        \[
            A = \frac{1}{2}
            \begin{pmatrix}
                0 & 1 & 1 \\
                1 & 0 & 1 \\
                1 & 1 & 0
            \end{pmatrix}
        \]

        is known to be \(\text{rank}_{\text{PSD}}(A) = 2\).

        ```python exec="1" source="above" result="text"
        import numpy as np
        from toqito.matrix_props import positive_semidefinite_rank

        A = 1/2 * np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]])
        print(positive_semidefinite_rank(A))
        ```

        The PSD rank of the identity matrix is the dimension of the matrix [@fawzi2015positive].

        ```python exec="1" source="above" result="text"
        import numpy as np
        from toqito.matrix_props import positive_semidefinite_rank

        print(positive_semidefinite_rank(np.identity(3)))
        ```

    """
    if not is_nonnegative(mat):
        raise ValueError("Matrix must be nonnegative.")
    if not is_square(mat):
        raise ValueError("Matrix must be square.")

    for k in range(1, max_rank + 1):
        if _check_psd_rank(mat, k):
            return k
    return None