Matrix

This section describes the matrix formulation. For the matrix formulation, the Amplify SDK provides matrix classes that are equivalents of quadratic polynomials on binary and Ising variables.

Note

The matrix form is used when dealing with tightly coupled problems where the number of terms is so large that it is inefficient to use polynomials. If you just want to have a general idea of how to use the Amplify SDK, you may skip this section.

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

\[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)\]

Define the matrix \(Q\) by placing the linear terms in the diagonal elements and the quadratic terms in the off-diagonal elements.

\[\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}\]

The relation between a polynomial and a matrix \(Q\) is expressed as follows:

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

Here, the variables are represented in vector form \(q^{\mathrm{T}} = \left(q_0, q_1, \cdots \right)\).

Quadratic polynomial of Ising variables

\[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)\]

As in the binary variable case, define the matrix \(J\) by placing the linear terms in the diagonal elements and the quadratic terms in the off-diagonal elements.

\[\begin{split}J = \left(\begin{array}{ccccc} h_{0} \\ & \ddots & & \LARGE J_{i,j} \\ & & h_{i} \\ & \huge 0 & & \ddots \\ & & & & \end{array}\right)\end{split}\]

The relation between a polynomial and a matrix \(J\) is expressed as follows:

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

Here, the variables are represented in vector form \(s^{\mathrm{T}} = \left(s_0, s_1, \cdots \right)\).

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

• BinaryMatrix

• IsingMatrix

• BinaryIntMatrix

• IsingIntMatrix

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, it is recommended to use BinaryMatrix and IsingMatrix which can handle real numbers.

Creating a Matrix Class

A matrix class is created 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 ones).

from amplify import BinaryMatrix

m = BinaryMatrix(3)

>>> m
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

The diagonal and off-diagonal elements correspond to the coefficients of the linear and quadratic terms of a quadratic 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

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

For quadratic polynomial on binary variables;

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

For quadratic polynomial on 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)

By default, the binary variables \(0, 1\) correspond to the Ising variables \(-1, 1\), respectively. You can flip this correspondence by giving False to the keyword argument ascending.

>>> m.to_BinaryMatrix(ascending=False)
([[1, 1, 0],
 [0, 0, -1],
 [0, 0, 0]], -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)

By default, the binary variables \(0, 1\) correspond to the Ising variables \(-1, 1\), respectively. You can flip this correspondence by giving False to the keyword argument ascending.

>>> m.to_IsingMatrix(ascending=False)
([[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. Like polynomial arrays for polynomial forms, matrix classes are recommended to be constructed using the powerful array operations of NumPy ndarray.

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