Matrix

This section describes the matrix classes that correspond to the quadratic polynomials of binary and Ising variables, respectively.

Matrix Representation of Quadratic Polynomials

The matrix representation of a quadratic polynomial is defined as an upper triangular matrix as follows:

Quadratic polynomials of binary variables

\[ \begin{align}\begin{aligned}f &= \sum_{i < j}{Q_{i,j} q_i q_j} + \sum_{i}{Q_{i,i} q_i} \quad \left(q_i \in \left\{ 0, 1\right\} \right)\\ &= q^{\mathrm{T}} Q q\end{aligned}\end{align} \]
\[\begin{split}Q = \left(\begin{array}{ccccc} Q_{0,0} \\ & \ddots & & \LARGE Q_{i,j} \\ & & Q_{i,i} \\ & \huge 0 & & \ddots \\ & & & & \end{array}\right)\end{split}\]

Quadratic polynomial of Ising variables

\[ \begin{align}\begin{aligned}f &= \sum_{i < j}{J_{i,j} s_i s_j} + \sum_{i}{h_i s_i} \quad \left(s_i \in \left\{ -1, +1\right\} \right)\\ &= s^{\mathrm{T}} J s - \mathrm{Tr}J + s^{\mathrm{T}} \cdot \operatorname{diag} J\end{aligned}\end{align} \]
\[ \begin{align}\begin{aligned}\begin{split}J = \left(\begin{array}{ccccc} h_{0} \\ & \ddots & & \LARGE J_{i,j} \\ & & h_{i} \\ & \huge 0 & & \ddots \\ & & & & \end{array}\right)\end{split}\\\operatorname{diag} J = \left(h_{0}, \cdots, h_i, \cdots \right)\end{aligned}\end{align} \]

The following matrix classes are provided to represent \(Q\) and \(J\) above:

BinaryMatrix and IsingMatrix are matrices whose variables are the binary variables \(\left\{0, 1\right\}\) and the Ising variables \(\left\{-1, 1\right\}\), respectively.

Note

BinaryIntMatrix and IsingIntMatrix are used when restricting the matrix elements to integer values. Since the matrix elements are limited to integers during calculations, unintended results may occur. For this reason, BinaryMatrix and IsingMatrix which can handle real numbers are usually recommended.

Constructing a Matrix Class

A matrix class is constructed as a size \(\times\) size zero matrix if size is specified as follows (henceforth, BinaryMatrix is used as an example, but the same is true for other matrix classes including Ising).

from amplify import BinaryMatrix

m = BinaryMatrix(3)
>>> m
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

The diagonal and off-diagonal terms correspond to the coefficients of the linear and quadratic parts of a second-order polynomial, respectively.

If an object of the same matrix class is given as the constructor argument, it will be copied.

from amplify import BinaryMatrix

m1 = BinaryMatrix(3)
m2 = BinaryMatrix(m1)
>>> m2
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

You can also construct a matrix class with a list of the initial values. The matrix elements can be given in the upper triangular parts or all elements as row major.

For a one-dimensional list, you need to specify the matrix size.

from amplify import BinaryMatrix
import numpy as np

m1 = BinaryMatrix(3, [1.0, 2.0, 3.0, 4.0, 5.0, 6.0])
m2 = BinaryMatrix(3, [1.0, 2.0, 3.0, 0.0, 4.0, 5.0, 0.0, 0.0, 6.0])
>>> m1
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m2
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]

If a two-dimensional list is given, the matrix size will be determined automatically.

from amplify import BinaryMatrix
import numpy as np

m1 = BinaryMatrix([[1.0, 2.0, 3.0], [4.0, 5.0], [6.0]])
m2 = BinaryMatrix([[1.0, 2.0, 3.0], [0.0, 4.0, 5.0], [0.0, 0.0, 6.0]])
>>> m1
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m2
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]

Matrix Operators

The most important operation on a matrix object is element access. We will create a matrix corresponding to a quadratic polynomial as follows:

\[f = q_0 q_1 - q_1 q_2 - 2 q_0 + q_2\]
from amplify import BinaryMatrix

m = BinaryMatrix(3)
m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
>>> m
[[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]]

The value of the m[i, j] element corresponds to the coefficient of \(q_i q_j\). Note that it is an upper triangular matrix, so \(i \le j\). We do not have access to the lower triangular part of the matrix.

Operators are defined for equivalence, addition, and subtraction between matrix objects, and for multiplication and division between matrix objects and constants. Compound substitution operations are also possible.

from amplify import BinaryMatrix

m1 = BinaryMatrix(3)

m1[0, 1] = 1
m1[1, 2] = -1
m1[0, 0] = -2
m1[2, 2] = 1

m2 = BinaryMatrix(m1)
>>> m1 == m2
True
>>> m1 == [[-2, 1, 0], [0, 0, -1], [0, 0, 1]]
True
>>> m1 + m2
[[-4, 2, 0],
 [0, 0, -2],
 [0, 0, 2]]
>>> m1 - m2
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
>>> m1 * 2
[[-4, 2, 0],
 [0, 0, -2],
 [0, 0, 2]]
>>> m1 / 2
[[-1, 0.5, 0],
 [0, 0, -0.5],
 [0, 0, 0.5]]

Methods in Matrix Classes

Evaluating Matrices

We can evaluate the polynomial expressed in terms of binary and Ising variables (given below), using the corresponding matrix object and variable vector.

Quadratic polynomials of binary variables

\[f = q^{\mathrm{T}} Q q\]

Quadratic polynomial of Ising variables

\[f = s^{\mathrm{T}} J s - \mathrm{Tr}J + s^{\mathrm{T}} \cdot \operatorname{diag} J\]

Lists and numpy.ndarray can be treated as vectors.

from amplify import BinaryMatrix
import numpy

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
>>> m
[[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]]
>>> m.evaluate([1, 0, 1])
-1.0

Matrix Resize

The size of a matrix object can be rescaled. When enlarged, the elements in the enlarged part are filled with \(0\) elements. When reduced, the elements in the reduced part are truncated.

from amplify import BinaryMatrix

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
>>> m
[[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]]
m.resize(6)
>>> m
[[-2, 1, 0, 0, 0, 0],
 [0, 0, -1, 0, 0, 0],
 [0, 0, 1, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0]]

Note

This method is destructive.

Matrix Size

The size of a matrix object can be obtained as follows.

from amplify import BinaryMatrix

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
>>> m.size()
3

Conversion to Binary Matrix

An Ising matrix can be converted to a binary matrix. A tuple of the transformed binary matrix and a constant term is returned.

from amplify import IsingMatrix

m = IsingMatrix(3)

m[0, 0] = -0.75
m[0, 1] = 0.25
m[1, 2] = -0.25
m[2, 2] = 0.25
>>> m.to_BinaryMatrix()
([[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]], 0.5)

Conversion to Ising Matrix

A binary matrix can be converted to an Ising matrix. A tuple of the transformed Ising matrix and a constant term is returned.

from amplify import BinaryMatrix

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
>>> m.to_IsingMatrix()
([[-0.75, 0.25, 0],
 [0, 0, -0.25],
 [0, 0, 0.25]], -0.5)

Conversion to Quadratic Polynomial

A matrix object can be converted to the corresponding polynomial class.

from amplify import BinaryMatrix

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
>>> m.to_Poly()
q_0 q_1 - q_1 q_2 - 2.000000 q_0 + q_2

The correspondence between the matrix classes from which they are converted and the converted polynomial classes is as follows:

Matrix class

polynomial class

BinaryMatrix

BinaryPoly

IsingMatrix

IsingPoly

BinaryIntMatrix

BinaryIntPoly

IsingIntPoly

IsingIntPoly

NumPy Integration

The interconversion between a matrix class and a NumPy array is possible.

A matrix class can be constructed from numpy.ndarray.

from amplify import BinaryMatrix
import numpy as np

a1 = np.array([1.0, 2.0, 3.0, 4.0, 5.0, 6.0])
m1 = BinaryMatrix(3, a1)
a2 = np.array([1.0, 2.0, 3.0, 0.0, 4.0, 5.0, 0.0, 0.0, 6.0])
m2 = BinaryMatrix(3, a2)
a3 = np.array([[1.0, 2.0, 3.0], [0.0, 4.0, 5.0], [0.0, 0.0, 6.0]])
m3 = BinaryMatrix(a3)
>>> m1
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m2
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m3
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m1 == a3
True
>>> m2 == a3
True
>>> m3 == a3
True

A matrix class can be converted to numpy.ndarray.

from amplify import BinaryMatrix
import numpy as np

a1 = np.array([[1.0, 2.0, 3.0], [0.0, 4.0, 5.0], [0.0, 0.0, 6.0]])
m1 = BinaryMatrix(a)
a2 = m1.to_numpy()
>>> a2
[[1. 2. 3.]
 [0. 4. 5.]
 [0. 0. 6.]]
>>> type(a2).__name__
ndarray