Integer matrices with large condition numbers

The following shows integer matrices with the largest possible condition number with the prescribed restrictions on their entries. Where possible, the matrix has been rewritten to be symmetric. The determinant of these matrices must be $\pm 1$. You can swap any two rows or columns, or multiply any row or column by $-1$ and get the same condition number.

There are two important points of the determinant being $1$: First, a matrix that has the largest condition number given the restrictions must have a non-zero determinant, but the smallest possible determinant of an integer matrix is $\pm 1$. This is because the determinant is the ratio of volumes, and you want the image of, for example, the unit ball to be compressed to the flattest possible "pancake" (an ellipsoid flattened in one direction), meaning, a determinant as close to zero as possible. Second, the solution to $A\textbf{u} = \textbf{b}$ for an integer vector $\textbf{b}$ must be an integer vector, which means that it is possible to work these out on the blackboard. In the examples below, the target vector will always be $\textbf{b}$ and the solution to $A\textbf{u} = \textbf{b}$ will be designated $\textbf{u}$.

The restriction will be that the matrix will have entries less than or equal to the given value $n$ in absolute value.

A 2 × 2 integer matrix with entries in absolute value no greater than $n = 1$

The eigenvalues of this matrix are $\phi$ and $-\phi^{-1}$ where $\phi = \frac{\sqrt{5} + 1}{2}$ is the golden ratio. The singular values are $\phi$ and $\phi^{-1}$. The condition number is $\phi^2$.

A 2 × 2 integer matrix with entries in absolute value no greater than $n = 2$

The eigenvalues of this matrix are $\phi^2$ and $\phi^{-2}$, as are the singular values. The condition number is $\phi^4$.

A 2 × 2 integer matrix with entries in absolute value no greater than $n \ge 3$

For $n \ge 3$, the pattern becomes regular:

The eigenvalues of this matrix are $n - 1 \pm \sqrt{n^2 + 1}$ with eigenvectors $\left(\begin{array}{c} n - 1 \\ 1 + \sqrt{n^2 - 2n + 2} \end{array}\right)$ and $\left(\begin{array}{c} n - 1 \\ 1 - \sqrt{n^2 - 2n + 2} \end{array}\right)$, respectively. The singular values are $n - 1 + \sqrt{n^2 + 1}$ and $\sqrt{n^2 + 1} - n + 1$. The condition number is thus $2n^2 - 4n + 3 + (2n - 2)\sqrt{n^2 - 2n + 2}$.

Example 2.1

To use this to demonstrate how the condition number magnifies errors in solutions, consider the left singular vector associated with the smallest singular value when $n = 11$, so $A = \left(\begin{array}{cc} 9 & 10 \\ 10 & 11 \end{array}\right)$. For this matrix, it is $\left(\begin{array}{r} -0.74145 \\ 0.67101 \end{array}\right)$. An integer vector that is close to a scalar multiple of this is $\textbf{b} = \left(\begin{array}{r} -1 \\ 1 \end{array}\right)$, and this will be our target vector. Solving $A\textbf{u} = \textbf{b}$ yeilds the solution $\textbf{u} = \left( \begin{array}{r} 21 \\ -19 \end{array} \right)$. Now, create a scalar multiple that is close to $\textbf{b}$: $\tilde{\textbf{b}} = \left( \begin{array}{r} -1.1 \\ 1.1 \end{array}\right) = 1.1\textbf{b}$ . Here, $\|\textbf{b} - \tilde{\textbf{b}}\|_2 = 0.14142 = 0.1\sqrt{2}$; however, when you solve $A\tilde{\textbf{u}} = \tilde{\textbf{b}}$, you get $\tilde{\textbf{u}} = \left( \begin{array}{r} -23.1 \\ -20.9 \end{array} \right)$, which, of course, shares the same relationship: $\tilde{\textbf{u}} = 1.1\textbf{u}$. However, $\|\textbf{u} - \tilde{\textbf{u}}\|_2 = 2.8320$ and $\frac{3.9484}{0.45772} = 20.025$, and thus, we see that a small error in $\textbf{b}$ is magnified by a factor greater than twenty.

Example 2.2

If you are looking for an example where it is not a scalar multiple, you can consider $\textbf{b} = \left(\begin{array}{r} 1 \\ 4 \end{array}\right)$ and $\tilde{\textbf{b}} = \left(\begin{array}{r} 0.1 \\ 4.8 \end{array}\right)$ where the solutions are $\textbf{u} = \left(\begin{array}{r} 29 \\ -26 \end{array}\right)$ and $\tilde{\textbf{u}} = \left(\begin{array}{r} 46.9 \\ -42.2 \end{array}\right)$, respectively, and $\frac{\textbf{u} - \tilde{\textbf{u}}}{\textbf{b} - \tilde{\textbf{b}}} = 20.049$. You will note that the difference between the vector $\textbf{b}$ and $\tilde{\textbf{b}}$ is close to a scalar multiple of the left singular vector associated with the smallest singular value.

Nice variations of these matrices

Nice variations of these matrices are $A = \left(\begin{array}{cc} n - 1 & n - 2 \\ -n & 1 - n \end{array}\right)$ that have eigenvalues $1$ and $-1$ with eigenvectors $\left(\begin{array}{r} -1 \\ 1 \end{array}\right)$ and $\left(\begin{array}{c} n - 2 \\ -n \end{array}\right)$, respectively.

A 3 × 3 integer matrix with entries in absolute value no greater than $n = 1$

Nice variations of this matrix

Interestingly the variation of this matrix $A = \left(\begin{array}{rrr} 1 & 1 & 1 \\ 1 & 1 & 0 \\ -1 & 0 & 1 \end{array}\right)$ has eigenvalues $1, 1, 1$, although this matrix is defective with only one eigenvector $\left(\begin{array}{r} 0 \\ -1 \\ 1 \end{array}\right)$.

A 3 × 3 integer matrix with entries in absolute value no greater than $n = 2$

Nice variations of this matrix

A nice variation of this matrix is $A = \left(\begin{array}{rrr} -1 & 1 & -2 \\ 2 & 2 & 1 \\ 2 & 1 & 2 \end{array}\right)$ that has eigenvalues $1$ and $1 \pm \sqrt{2}$ with eigenvectors $\left(\begin{array}{r} -3 \\ 2 \\ 4 \end{array}\right)$, $\left(\begin{array}{c} -1 \\ 2 + \sqrt{2} \\ 2 + \sqrt{2} \end{array}\right)$, and $\left(\begin{array}{c} -1 \\ 2 - \sqrt{2} \\ 2 - \sqrt{2} \end{array}\right)$, respectively.

Another nice variation of this matrix is $A = \left(\begin{array}{rrr} 1 & 1 & -2 \\ -2 & 2 & 1 \\ -2 & 1 & 2 \end{array}\right)$ that has eigenvalues $1$ and $2 \pm \sqrt{3}$ with eigenvectors $\left(\begin{array}{r} 3 \\ 4 \\ 2 \end{array}\right)$, $\left(\begin{array}{c} -1 \\ 1 + \sqrt{3} \\ 1 + \sqrt{3} \end{array}\right)$, and $\left(\begin{array}{c} -1 \\ 1 - \sqrt{3} \\ 1 - \sqrt{3} \end{array}\right)$, respectively.

A 3 × 3 integer matrix with entries in absolute value no greater than $n = 3$

For $n = 3$, we have $A = \left(\begin{array}{rrr} -3 & 3 & 1 \\ 3 & 1 & 2 \\ 2 & 3 & 3 \\ \end{array}\right)$ where the condition number is approximately $155.736$. $A^{-1} = \left(\begin{array}{rrr} -3 & -6 & 5 \\ -5 & -11 & 9 \\ 7 & 15 & -12 \\ \end{array}\right)$.

A 3 × 3 integer matrix with entries in absolute value no greater than $n = 4$

The singular values are $8.57, 5.53$ and $0.02$. A small change in the direction of the left singular vector corresponding to $0.02$ will see a significant change in the solution to $A\textbf{u} = \textbf{b}$ for a given target vector $\textbf{b}$.

Example 3.4.1

To use this to demonstrate how the condition number magnifies errors in solutions, consider the left singular vector associated with the smallest singular value. For this matrix, it is $\left(\begin{array}{r} -0.19574 \\ -0.67849 \\ 0.70806 \end{array}\right)$. An integer vector that is close to a scalar multiple of this is $\textbf{b} = \left(\begin{array}{r} -2 \\ -7 \\ 7 \end{array}\right)$, and this will be our target vector. Solving $A\textbf{u} = \textbf{b}$ yeilds the solution $\textbf{u} = \left( \begin{array}{r} -58 \\ -357 \\ 313 \end{array} \right)$. Now, create a scalar multiple that is close to $\textbf{b}$: $\tilde{\textbf{b}} = \left( \begin{array}{r} -2.2 \\ -7.7 \\ 7.7 \end{array}\right) = 1.1\textbf{b}$ . Here, $\|\textbf{b} - \tilde{\textbf{b}}\|_2 = 1.0100$; however, when you solve $A\tilde{\textbf{u}} = \tilde{\textbf{b}}$, you get $\tilde{\textbf{u}} = \left( \begin{array}{r} -63.8 \\ -392.7 \\ 344.3 \end{array} \right)$, which, of course, shares the same relationship: $\tilde{\textbf{u}} = 1.1\textbf{u}$. However, $\|\textbf{u} - \tilde{\textbf{u}}\|_2 = 47.831$ and $\frac{47.831}{1.0100} = 47.360$, and thus, we see that a small error in $\textbf{b}$ is magnified by a factor of almost fifty.

Example 3.4.2

If you are looking for an example where it is not a scalar multiple, you can consider $\textbf{b} = \left(\begin{array}{r} 4 \\ 5 \\ -4\end{array}\right)$ and $\tilde{\textbf{b}} = \left(\begin{array}{r} 3.9 \\ 4.5 \\ -3.6 \end{array}\right)$ where the solutions are $\textbf{u} = \left(\begin{array}{r} 63 \\ 220 \\ -229 \end{array}\right)$ and $\tilde{\textbf{u}} = \left(\begin{array}{r} 57.0 \\ 199.2 \\ -207.3 \end{array}\right)$, respectively, and $\frac{\textbf{u} - \tilde{\textbf{u}}}{\textbf{b} - \tilde{\textbf{b}}} = 47.297$. You will note that the difference between the vector $\textbf{b}$ and $\tilde{\textbf{b}}$ is close to a scalar multiple of the left singular vector associated with the smallest singular value.

Nice variations of this matrix

Interestingly the variation of this matrix $A = \left(\begin{array}{rrr} 3 & 4 & -4 \\ -2 & -3 & 4 \\ 4 & 3 & 3 \end{array}\right)$ has eigenvalues $1, 1, 1$, although this matrix is defective with only one eigenvector $\left(\begin{array}{r} -2 \\ 2 \\ 1 \end{array}\right)$.

A nice variation of this matrix is $A = \left(\begin{array}{rrr} 3 & 4 & -3 \\ 4 & -2 & 3 \\ 4 & -3 & 4 \end{array}\right)$ that has eigenvalues $1$ and $2 \pm \sqrt{5}$ with eigenvectors $\left(\begin{array}{r} -3 \\ 18 \\ 22 \end{array}\right)$, $\left(\begin{array}{c} 1 \\ \sqrt{5} - 1 \\ \sqrt{5} - 1 \end{array}\right)$, and $\left(\begin{array}{c} -1 \\ \sqrt{5} + 1 \\ \sqrt{5} + 1 \end{array}\right)$, respectively.

A 3 × 3 integer matrix with entries in absolute value no greater than $n = 5$

The singular values are $11.26, 7.22$ and $0.01$.

Example 3.5.1

Consider the perturbed matrix $\tilde{A} = \left(\begin{array}{rrr} -5 & 5 & 2\phantom{.000} \\ 3 & 5 & 5.001 \\ 5 & 4 & 5\phantom{.000} \end{array} \right)$, where only one entry is changed by $0.001$. $|||A - \tilde{A}|||_2 = 0.001$. If we let the target vector be an integer vector close to the left singular vector corresponding to the smallest singular value, we have $\textbf{b} = \left( \begin{array}{r} 1 \\ -4 \\ 3 \end{array} \right)$, and we observe that the solutions to $A\textbf{u} = \textbf{b}$ and $\tilde{A}\tilde{u} = \textbf{b}$ are $\textbf{u} = \left( \begin{array}{r} -118 \\ -243 \\ 313 \end{array} \right)$, $\tilde{\textbf{u}} = \left( \begin{array}{r} -123.572 \\ -254.471 \\ 327.749 \end{array} \right)$, and $\|\textbf{u} - \tilde{\textbf{u}}\|_2 = 19.498$.

Example 3.5.2

Consider the perturbed matrix $\tilde{A} = \left(\begin{array}{rrr} -4.9 & 5\phantom{.0} & 2\phantom{.0} \\ 3\phantom{.0} & 5\phantom{.0} & 5\phantom{.0} \\ 5.1 & 4\phantom{.0} & 5\phantom{.0} \end{array} \right)$. $|||A - \tilde{A}|||_2 = 0.1\sqrt{2} = 0.1414$. If we let the target vector be an integer vector close to the left singular vector corresponding to the smallest singular value, we have $\textbf{b} = \left( \begin{array}{r} 1 \\ -4 \\ 3 \end{array} \right)$, and we observe that the solutions to $A\textbf{u} = \textbf{b}$ and $\tilde{A}\tilde{u} = \textbf{b}$ are $\textbf{u} = \left( \begin{array}{r} -118 \\ -243 \\ 313 \end{array} \right)$, $\tilde{\textbf{u}} = \left( \begin{array}{r} 118\phantom{.0} \\ 240.8 \\ -312.4 \end{array} \right)$, and $\|\textbf{u} - \tilde{\textbf{u}}\|_2 = 825.16$, and thus, the error has been magnified by a factor of $5834.7$, for as you can see, $\textbf{u} \approx -\tilde{\textbf{u}}$.

A 3 × 3 integer matrix with entries in absolute value no greater than $n \geq 6$

For $n = 6$, we have $A = \left(\begin{array}{rrr} -5 & 6 & 6 \\ 5 & 6 & 5 \\ 6 & 5 & 4 \\ \end{array}\right)$ where the condition number is approximately $1600.27$.

For $n = 7$, we have $A = \left(\begin{array}{rrr} -6 & 7 & 7 \\ 6 & 7 & 6 \\ 7 & 6 & 5 \\ \end{array}\right)$ where the condition number is approximately $2659.6$.

For $n = 8$, we have $A = \left(\begin{array}{rrr} -7 & 8 & 8 \\ 7 & 8 & 7 \\ 8 & 7 & 6 \\ \end{array}\right)$ where the condition number is approximately $4108.9$.

For $n = 9$, we have $A = \left(\begin{array}{rrr} -8 & 9 & 9 \\ 8 & 9 & 8 \\ 9 & 8 & 7 \\ \end{array}\right)$ where the condition number is approximately $6009.81$. This is my personal favorite, as it has the largest condition number for an integer matrix with only single digits. Visually, you can see quite clearly that two columns are almost identical (there is only $3^\circ$ between them, while the first is much closer to $90^\circ$ relative to the second and third columns: the angle between the first and the second and third are approximately $71^\circ$ and $74^\circ$, respectively.

The eigenvalues are $21.2613$, $-13.2649$, and $0.0035457$. The singular values are $21.2833$, $13.2673$, and $0.00354143$. The left singular vector associated withthe smallest singular value is $\left(\begin{array}{r} 0.0828 \\ -0.7072 \\ 0.7022 \\ \end{array}\right)$ and an integer vector close to a scalar multiple of this vector is $\left(\begin{array}{r} 2 \\ -17 \\ 17 \\ \end{array}\right)$, although $\left(\begin{array}{r} 1 \\ -8 \\ 8 \\ \end{array}\right)$ is also close.

For $n = 10$, we have $A = \left(\begin{array}{rrr} -9 & 10 & 10 \\ 9 & 10 & 9 \\ 10 & 9 & 8 \\ \end{array}\right)$ where the condition number is approximately $8423.7$.

The pattern suggest $A = \left(\begin{array}{ccc} 1 - n & n & n \\ n - 1 & n & n - 1 \\ n & n - 1 & n - 2 \\ \end{array}\right)$ and the condition number appears to approach $10n^3$ as $n \rightarrow \infty$.

The pattern suggests a hopeful symmetric matrix $A = \left(\begin{array}{ccc} 1 - n & n & n \\ n & n & n - 1 \\ n & n - 1 & n - 2 \\ \end{array}\right)$ but the condition number of this appears to approach $10n^2$ as $n \rightarrow \infty$.

A 4 × 4 integer matrix with entries in absolute value no greater than $n = 1$

This matrix was chosen for its real eivenvalues: $1 \pm \sqrt{2}, -\phi$ and $\phi^{-1}$.

Example 4.1.1

To use this to demonstrate how the condition number magnifies errors in solutions, consider the left singular vector associated with the smallest singular value. For this matrix, it is $\left(\begin{array}{r} -0.75810 \\ 0.53345 \\ 0.32969 \\ -0.17896 \end{array}\right)$. An integer vector that is close to a scalar multiple of this is $\textbf{b} = \left(\begin{array}{r} -4 \\ 3 \\ 2 \\ -1 \end{array}\right)$, and this will be our target vector. Solving $A\textbf{u} = \textbf{b}$ yeilds the solution $\textbf{u} = \left( \begin{array}{r} 7 \\ -21 \\ 30 \\ -13 \end{array} \right)$. Now, create a scalar multiple that is close to $\textbf{b}$: $\tilde{\textbf{b}} = \left( \begin{array}{r} -4.4 \\ 3.3 \\ 2.2 \\ -1.1 \end{array}\right) = 1.1\textbf{b}$ . Here, $\|\textbf{b} - \tilde{\textbf{b}}\|_2 = 0.54772$; however, when you solve $A\tilde{\textbf{u}} = \tilde{\textbf{b}}$, you get $\tilde{\textbf{u}} = \left( \begin{array}{r} 7.7 \\ -23.1 \\ 33 \\ -14.3 \end{array} \right)$, which, of course, shares the same relationship: $\tilde{\textbf{u}} = 1.1\textbf{u}$. However, $\|\textbf{u} - \tilde{\textbf{u}}\|_2 = 3.9484$ and $\frac{3.9484}{0.45772} = 7.2088$, and thus, we see that a small error in $\textbf{b}$ is magnified by a factor greater than seven.

Example 4.1.2

If you are looking for an example where it is not a scalar multiple, you can consider $\textbf{b} = \left(\begin{array}{r} 0 \\ -2 \\ 2 \\ -2 \end{array}\right)$ and $\tilde{\textbf{b}} = \left(\begin{array}{r} -0.1 \\ -1.7 \\ 1.6 \\ -1.8 \end{array}\right)$ where the solutions are $\textbf{u} = \left(\begin{array}{r} -18 \\ 12 \\ 8 \\ -4 \end{array}\right)$ and $\tilde{\textbf{u}} = \left(\begin{array}{r} -15.0 \\ 9.9 \\ 6.7 \\ -3.3 \end{array}\right)$, respectively, and $\frac{\textbf{u} - \tilde{\textbf{u}}}{\textbf{b} - \tilde{\textbf{b}}} = 7.2088$. You will note that the difference between the vector $\textbf{b}$ and $\tilde{\textbf{b}}$ is close to a scalar multiple of the left singular vector associated with the smallest singular value.

A 4 × 4 integer matrix with entries in absolute value no greater than $n = 2$

A 5 × 5 integer matrix with entries in absolute value no greater than $n = 1$