toqito.matrix_props.factor_width

Determine the factor width of a positive semidefinite matrix.

Module Contents

toqito.matrix_props.factor_width.factor_width(mat, k, *, solver='SCS', solver_kwargs=None, tol=1e-08)[source]

Decide whether a positive semidefinite matrix has factor width at most (k).

The factor width of a matrix is the minimal value of (k) for which it admits a decomposition (M = sum_j v_j v_j^*) with each (v_j) supported on at most (k) coordinates. This routine implements the low-rank algorithm in [@Johnston_2025_Complexity].

Examples

The matrix (operatorname{diag}(1, 1, 0)) has factor width at most (1).

```python exec=”1” source=”above” import numpy as np from toqito.matrix_props import factor_width

diag_mat = np.diag([1, 1, 0]) result = factor_width(diag_mat, k=1) print(result[“feasible”]) ```

Conversely, the rank-one matrix (begin{pmatrix} 1 & 1 \ 1 & 1 end{pmatrix}/2) is not (1)-factorable.

```python exec=”1” source=”above” import numpy as np from toqito.matrix_props import factor_width

hadamard = np.array([[1, 1], [1, 1]], dtype=np.complex128) / 2 result = factor_width(hadamard, k=1) print(result[“feasible”]) ```

Parameters:

  • mat (numpy.ndarray) – Positive semidefinite matrix to test.

  • k (int) – Target factor width bound.

  • solver (str | None) – CVXPY solver name (defaults to “SCS”).

  • solver_kwargs (dict | None) – Additional keyword arguments forwarded to cvxpy.Problem.solve.

  • tol (float) – Numerical tolerance used for rank computations and duplicate detection.

Returns:

Dictionary with keys feasible (boolean flag), status (solver status string), factors (list of PSD matrices whose sum equals mat when feasible), and subspaces (orthonormal bases spanning the subspaces used in the decomposition).

Return type:

dict