39
$\begingroup$

Olga Tausky-Todd had once said that

"If an assertion about matrices is false, there is usually a 2x2 matrix that reveals this."

There are, however, assertions about matrices that are true for $2\times2$ matrices but not for the larger ones. I came across one nice little example yesterday. Actually, every student who has studied first-year linear algebra should know that there are even assertions that are true for $3\times3$ matrices, but false for larger ones --- the rule of Sarrus is one obvious example; a question I answered last year provides another.

So, here is my question. What is your favourite assertion that is true for small matrices but not for larger ones? Here, $1\times1$ matrices are ignored because they form special cases too easily (otherwise, Tausky-Todd would have not made the above comment). The assertions are preferrably simple enough to understand, but their disproofs for larger matrices can be advanced or difficult.

$\endgroup$

18 Answers 18

29
$\begingroup$

Any two rotation matrices commute.

$\endgroup$
  • 4
    $\begingroup$ Yes! This one should be classic. $\endgroup$ – user1551 Nov 23 '13 at 7:24
  • 6
    $\begingroup$ But the notion of rotation matrices itself seems closely tied to real inner product spaces, and to low dimensions; it is not even quite clear to me exactly what is a general rotation matrix. An element of $\mathbf{SO}(n,\Bbb R)$? $\endgroup$ – Marc van Leeuwen Nov 23 '13 at 8:34
  • $\begingroup$ @MarcvanLeeuwen: Rotation matrices don't commute in three dimensions. $\endgroup$ – Javier Nov 24 '13 at 20:07
  • $\begingroup$ @JavierBadia: What exactly made you think I was not aware of that? I also know that in whatever (reasonable) way you define them they won't always commute in any given dimension$~n>2$, because $\mathbf{SO}(n,\Bbb R)$ is not commutative. But there still remains the question of what exactly "rotations" are defined to be in dimensions$~n>3$. $\endgroup$ – Marc van Leeuwen Nov 25 '13 at 6:03
  • $\begingroup$ @MarcvanLeeuwen: The reason I made my comment is that yours seemed to imply that this isn't a very good example because it's not evident how to define a rotation matrix for $n > 2$ dimensions. I just wanted to make clear that $3$-dimensional rotation matrices are easy to define and don't commute, that's all. $\endgroup$ – Javier Nov 25 '13 at 14:12
26
$\begingroup$

I like this one: two matrices are similar (conjugate) if and only if they have the same minimal and characteristic polynomials and the same dimensions of eigenspaces corresponding to the same eigenvalue. This statement is true for all $n\times n$ matrices with $n\leq6$, but is false for $n\geq7$.

$\endgroup$
  • 7
    $\begingroup$ Nice example +1. However, given general theory this can be seen to be more a statement about partitions (or their Young diagrams) than about matrices, namely "a Young diagram is determined by its size and the lengths of its first row and column"; this is of course quite false in general by one needs $3+3-1=5$ squares in the first row+column and two more squares to make the smallest counterexample, whence the $7$. $\endgroup$ – Marc van Leeuwen Nov 23 '13 at 8:30
  • 3
    $\begingroup$ Right, but nevertheless this seemed like a nice example $\endgroup$ – Dennis Gulko Nov 23 '13 at 9:56
  • $\begingroup$ How exactly are we partitioning the eigenvalues? Into Jordan blocks? If so, doesn't the dimension of the (generalized?) eigenspace give more information than the size of just one row? $\endgroup$ – Nishant Aug 4 '14 at 16:36
11
$\begingroup$

A matrix is called doubly stochastic if all its entries are nonnegative and each row and column sums to 1. A matrix is called orthostochastic if it is the entry-wise square of some orthogonal matrix. In general, it is easy to see that every orthostochastic matrix is doubly stochastic.

For $2\times 2$ matrices, every doubly stochastic matrix is orthostochastic, but for $3\times 3$ matrices (and hence anything larger) we have the counterexample $$ \frac{1}{2}\left(\begin{matrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix}\right)$$

$\endgroup$
  • 1
    $\begingroup$ Entrywise squares of orthogonal matrices form a subset of orthostochastic matrices, but the inclusion in the opposite direction is true only for 2x2 matrices ... nice example. +1. $\endgroup$ – user1551 Nov 23 '13 at 15:56
  • 1
    $\begingroup$ @user1551: It depends on the definition of orthostochastic that you use. In the papers I've read, this is how orthostochastic matrices are defined, and the term unistochastic refers to matrices which are the entry-wise product of a unitary matrix with its complex conjugate. $\endgroup$ – J. Loreaux Nov 23 '13 at 19:30
10
$\begingroup$

The irreducible representations of $GL_n(\mathbb F_q)$ are well understood for $n=1, 2$, but there is still a lot that isn't known for $n \geq 3$.

$\endgroup$
  • 1
    $\begingroup$ this answer deserves, a +1 great $\endgroup$ – Stahl Dec 3 '13 at 22:13
  • 5
    $\begingroup$ @Stahl, then why didn't you give one? $\endgroup$ – JMCF125 Apr 4 '14 at 15:42
  • 3
    $\begingroup$ The existence of "a lot that isn't known" is not really the failing of an assertion for larger matrices. Maybe you could give a concrete example of something known about representations of $GL_2(\Bbb F_q)$ that fails for $GL_n$ with $n>2$. $\endgroup$ – Marc van Leeuwen Jul 27 '17 at 8:12
7
$\begingroup$

Edit: I found more examples from questions/answers on this site. Unless otherwise specified, the matrix we concern is $n\times n$.

  1. Let $M=\pmatrix{A&B\\ C&D}$, where the subblocks $A,B,C,D$ are real square matrices. Then $\det(M)=\det(AD-BC)$. This is true when $M$ is $2\times2$, but in general false for larger matrices. But one may argue that this is not a valid example, because the statement is true only when the subblocks are $1\times1$ matrices.
  2. If $A$ is a singular matrix over a field, then every positive integer power of $A$ is a scalar multiple of $A$. This is true for $n=2$ but not for larger $n$s.
  3. If $A$ is a real symmetric matrix with all diagonal entries equal to $1$ and all off-diagonal entries lying inside $[-1,1]$, then $\det(A)\le1$. This is true for $n=2,3$ and false for $n=5$. It's probably true when $n=4$ but I haven't investigated the problem any further.
  4. Let ${\cal B}$ denotes the set of all 0-1 matrices and let $M=\max_{A\in \cal B}\det A$. For every $d\in\{0,1,\ldots,M\}$, there exists $A\in{\cal B}$ such that $\det(A)=d$. This is true up to $n=6$, false for $n=7$ and there is no known result for $n\ge22$.
  5. (See Omran Kouba's answer to a related question.) If $X,Y\in M_n(\mathbb R)$, then $\det(X^2+Y^2)\ge\det(XY-YX)$. This is true for $n=2$ but not for larger $n$s. By the way, the analogous inequality $\det(X^TX+Y^TY)\ge\det(X^TY-Y^TX)$ does hold for all $n$.
$\endgroup$
  • 2
    $\begingroup$ The derivative formula does generalize, it's just a bit more subtle: $\det M = \det(A)\det(D - CA^{-1} B)$ holds when $A$ is an invertible $n\times n$ matrix, $B$ is an $n\times m$ matrix, $C$ an $m\times n$ matrix, and $D$ an $m\times m$ matrix. $\endgroup$ – Stahl Nov 23 '13 at 7:12
  • 1
    $\begingroup$ I think this example disqualifies somewhat for two reasons: (a) the statement is meaningless (vacuously true) for odd size square matrices, and (b) the form of the $2\times2$ determinant has been explicitly built into the property, so its truth for $2\times2$ matrices is trivial. $\endgroup$ – Marc van Leeuwen Nov 23 '13 at 8:12
  • 1
    $\begingroup$ @MarcvanLeeuwen Agree. I posted this answer only to lure the others to post theirs. ;-D $\endgroup$ – user1551 Nov 23 '13 at 8:19
6
$\begingroup$

Here's a false statement I ran into recently that requires a $3 \times 3$ counterexample: "if $A$ is normal, then so is every principal submatrix of $A$". It is in a sense "tempting" to believe this because the analogous statement applies to Hermitian and skew-Hermitian matrices.

Simplest counterexample: $$ A = \pmatrix{0&1&0\\0&0&1\\1&0&0} $$

$\endgroup$
  • 2
    $\begingroup$ +1, but in the same sense that my example is not really a valid example, your example isn't too, because every proper principal submatrix of a 2x2 matrix is 1x1. $\endgroup$ – user1551 Nov 23 '13 at 7:14
6
$\begingroup$

Referring to the question Can commuting matrices $X,Y$ always be written as polynomials of some matrix $A$? it can be said that even the stronger property "for two commuting matrices one of them can always be written as a polynomial in the other" holds for $2\times2$ matrices (in fact, unless one is a scalar multiple of the identity both can be written as a polynomial in the other one), but not for $3\times3~$matrices. The weaker property of the question referred to (which allows a third matrix to be used to express both commuting matrices) also turns out to have counterexamples from size$~3\times3$ on, but they are sufficiently rare that I initially thought that weaker property would be generally valid.

$\endgroup$
6
$\begingroup$

Only for $2\times2$ matrices $A$ it's true that $\mathrm{adj}(A)=\mathrm{trace}(A)I-A$.

$\endgroup$
  • 2
    $\begingroup$ Given that this already fails for $1\times1$ matrices, I don't think this really matches the criterion "true for small matrices but not for larger ones" of the question. $\endgroup$ – Marc van Leeuwen Jul 27 '17 at 7:44
5
$\begingroup$

Recently, I come up with the following conjecture, which is proved to be true for small matrices and false for large matrices.

Conjecture. Let $E \in \mathbb{R}^{d\times d}$ be the matrix of ones and $M \in \mathbb{R}^{d\times d}$ be a bounded matrix representing a metric. That is, $M$ satisfies the following conditions:

  • $1 \geq M_{ij} \geq 0\ $ for $\ 1 \leq i, j \leq d$
  • $M_{ij} = 0\ \Leftrightarrow\ i = j$
  • $M_{ij} = M_{ji}$
  • $M_{ij} + M_{jk} \geq M_{ik}$ for $1 \leq i, j, k \leq d$

Then the matrix $A = E - M$ is positive semi-definite.


When $d = 2$, $M$ and $A$ respectively have the form $$ M = \begin{bmatrix} 0 & a \\ a & 0 \end{bmatrix},\quad A = \begin{bmatrix} 1 & 1 - a \\ 1 - a & 1 \end{bmatrix} $$ with $0 < a \leq 1$. For any $x \in \mathbb{R}^2$, $$ x^TAx = x_1^2 + x_2^2 + 2(1-a)x_1x_2 = (1-a)(x_1 + x_2)^2 + ax_1^2 + ax_2^2 \geq 0 $$ Thus the conjecture is true for $d = 2$.


When $d = 3$, $M$ and $A$ respectively have the form $$ M = \begin{bmatrix} 0 & a & b \\ a & 0 & c \\ b & c & 0 \end{bmatrix},\quad A = \begin{bmatrix} 1 & 1 - a & 1 - b \\ 1 - a & 1 & 1 - c \\ 1 - b & 1-c & 1 \end{bmatrix} $$ with $0 < a, b, c \leq 1$. Without loss of generality, we assume $c \geq a$ and $c \geq b$. For $\forall x \in \mathbb{R}^3$, \begin{align} x^TAx\ &=\ x_1^2 + x_2^2 + x_3^2 + 2(1-a)x_1x_2 + 2(1-b)x_1x_3 + 2(1-c)x_2x_3 \\ &=\ (1-c)(x_1 + x_2 + x_3)^2 + cx_1^2 + cx_2^2 + cx_3^2 + 2(c-a)x_1x_2 + 2(c-b)x_1x_3 \\ &=\ (1 - c)(x_1 + x_2 + x_3)^2 + (c-a)(x_1 + x_2)^2 + ax_1^2 + ax_2^2 + cx_3^2 + 2(c-b)x_1x_3 \\ &=\ (1 - c)(x_1 + x_2 + x_3)^2 + (c-a)(x_1 + x_2)^2 + (c-b)(x_1 + x_3)^2 \\ &\ \ \quad \quad + (\color{red}{a + b - c})x_1^2 + ax_2^2 + bx_3^2 \\ &\geq\ 0 \end{align} Note that $a + b - c \geq 0$ by triangle inequality. Therefore, the conjecture holds at $d = 3$.


When $d = 4$, the proof becomes harder. Using a computer, I enumerate all metric matrices whose non-diagonal elements have values from $\{\frac{1}{1000}, \frac{2}{1000}, \cdots, \frac{1000}{1000}\}$. The result shows that all these matrices are positive semi-definite. So the conjecture seems to be true for $d = 4$.


For $d = 5$, I find the following counterexample whose eigenvalues are $2.428$, $-0.089$, $0.5$, $1.161$ and $1$. $$ M = \begin{bmatrix} 0 & 0.5 & 0.5 & 0.5 & 1 \\ 0.5 & 0 & 0.5 & 0.5 & 1 \\ 0.5 & 0.5 & 0 & 1 & 0.5 \\ 0.5 & 0.5 & 1 & 0 & 0.5 \\ 1 & 1 & 0.5 & 0.5 & 0 \end{bmatrix},\quad A = \begin{bmatrix} 1 & 0.5 & 0.5 & 0.5 & 0 \\ 0.5 & 1 & 0.5 & 0.5 & 0 \\ 0.5 & 0.5 & 1 & 0 & 0.5 \\ 0.5 & 0.5 & 0 & 1 & 0.5 \\ 0 & 0 & 0.5 & 0.5 & 1 \end{bmatrix} $$ So the conjecture does hold in general for $d \geq 5$.

$\endgroup$
4
$\begingroup$

Matrices of size $2 \times 2$ are fully understood in terms of the number of elementary multiplications required to multiply two matrices. This is not the case for even slightly bigger matrices. There is a gap between lower and upper bound for the number of multiplications required.

The product of two $2 \times 2$ matrices (denoted as case $<2,2,2>$) can be computed in $7$ elementary multiplications. Winograd showed that seven is actually the minimum number or multiplications required.

Bläser obtained a lower bound of $19$ multiplications for the product of $3 \times 3$ matrices. However, the best known algorithm for the non-commutative product needs $23$ multiplications. The solution of Laderman has not been improved since 1976. Recent work confirmed, that there are many other algorithms with $23$ multiplications. The case $<2,2,3>$ (equivalent to $<2,3,2>$ and $<3,2,2>$) currently has a lower bound of $10$ and a known solution with $11$ multiplications. Hopcroft and Kerr published an algorithm for $<2,3,3>$ which requires $15$ multiplications, while the lower bound is $14$.

$\endgroup$
  • $\begingroup$ Is counting elementary operations (like multiplications) considered to be of practical importance, these days, or is this just a theoretical topic? Back in my youth, we used to do this all the time in our attempts to improve performance. But, nowadays, my impression is that memory locality and copying times are just as important as flops. Is that true, do you think? $\endgroup$ – bubba Jun 8 '14 at 9:25
  • $\begingroup$ @bubba: yes, you have a point there. It requires rather high matrix dimensions to beat the classical matrix multiplication method by a Strassen-style method. But memory and cache tuning are restricted to linear acceleration factors, while it would lead to an exponential speedup, if we could multiply - for example - two $3\times3$ matrices with 21 or fewer elementary products. Apart from that: Research in the area of matrix multiplication has indeed created quite a few theoretical insights. $\endgroup$ – Axel Kemper Jun 8 '14 at 18:26
  • $\begingroup$ I don't think that a concrete statement about the complexity of matrix multiplication, like "multiplication can be performed using at most 7 scalar multiplications" qualifies as an "assertion that is true for small matrices but not for larger ones", since it is not a statement about the matrices themselves. Even more so, "the complexity of matrix multiplication is fully understood" is not even a mathematical assertion, and it is unclear what it would mean to say that it fails for larger matrices. $\endgroup$ – Marc van Leeuwen Jul 27 '17 at 8:03
4
$\begingroup$

The statement:

Let $M\in\Bbb R^{n\times n}$ be symmetric. If $\det(M)>0$ and $\operatorname{Tr}(M)>0$, then $M$ is positive definite.

Is true for $n=2$ (note that $\det(M)=\lambda_1\lambda_2$ and $\operatorname{Tr}(M)>0=\lambda_1+\lambda_2$, where $\lambda_i$ are the eigenvalues of $M$) but wrong for $n>2$ (e.g. if $M$ is a diagonal matrix where $2$ diagonal elements are small and strictly negative).

Note that a similar statement can be maid about positive semi-definite matrices.

$\endgroup$
4
$\begingroup$

Interesting although quite elementary is property for matrices made from consecutive integers numbers (or more generally from values of arithmetic progression) where rows make an arithmetic progression.

Only $2 \times 2$ matrices made from consecutive integers numbers are non-singular, matrices of higher dimension are singular.

For example matrix $\begin{bmatrix} 1 & 2\\ 3 & 4 \\ \end{bmatrix}$ is non-singular,
but matrices like $\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}$, $\begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{bmatrix}$, $\dots$ are singular.

This can be applied for easy generating of singular matrices if needed.

$\endgroup$
3
$\begingroup$

For matrices of order 2, we have a simple formula for the determinant of the sum of 2 matrices:

If $A,B$ are matrices of order 2 then $$\det(A+B)=\det(A)+\det(B)+\operatorname{tr}(A\operatorname{adj}(B)),$$ where $\operatorname{adj}(B)$ is the classical adjoint of $B$.

$\endgroup$
3
$\begingroup$

Preliminary: let $A$ be real square matrix.

Definition: $A$ is called (positive) stable if $\sigma(A)\subset\mathbb{C}_+$.

Theorem (Lyapunov): $A$ is stable iff $\exists$ pos.-def. $H\colon A^TH+HA$ is pos.-def.

Definition: $A$ is called diagonally stable if $\exists$ pos.-def. diagonal $D\colon A^TD+DA$ is pos.-def.

Definition: $A$ is called $P$-matrix if all principal minors are positive.

The main contribution: the statement

$A$ is diagonally stable $\Leftrightarrow$ $A$ is a $P$-matrix

is true only for $1\times 1$ and $2\times 2$ matrices. For $3\times 3$ and higher, $\Leftarrow$, in general, is false, however there are some special cases (acyclic matrices, $Z$-matrices) when it is true.

P.S. It is still an open problem to characterize diagonal stability in general. The case $3\times 3$ is known (not sure about $4\times 4$).

$\endgroup$
3
$\begingroup$

Claim: There is an algebraic procedure that terminates in finite steps to obtain the eigenvalues of a general $n\times n$ matrix.

This is true for $n \leq 4$ but fails for $n \geq 5$, thanks to Abel-Ruffini.

$\endgroup$
2
$\begingroup$

Computing the determinant (over an arbitrary ring, not just fields) is easy.

Sure, trivial for $2\times 2$ and $3\times 3$, but many young students don't realize that the naive approach will be unbearably slow (by hand) already for $5\times 5$.

In case anyone objects to this being a rigorous mathematical statement, you can phrase it as ".. Is not polynomial-time".

$\endgroup$
2
$\begingroup$

Let $n\geq 2$ and $A,B\in M_n(\mathbb{C})$ be s.t. $A^2+B^2+2AB=0_n$.

Then $AB=BA$ $\Leftrightarrow n=2$.

For $\Leftarrow$: see my post in What can be said if $A^2+B^2+2AB=0$ for some real $2\times2$ matrices $A$ and $B$?

For $\Rightarrow$: when $n\geq 3$, there are $A,B$ s.t. $A^2=0,B^2=0,AB=0,BA\not= 0$.

$\endgroup$
2
$\begingroup$

Let $A \in M_2(\mathbb R)$, $A$ is invertible or $A$ is nilpotent or $A$ is diagonalizable

Proof: Let $\chi_A$ be its characteristic polynomial, then $\chi_A = X^2-$ tr$(A)X + \det A$.

If $\det A \neq 0$ then $A$ is invertible.

Else if tr$(A) = 0$, then by Cayley-Hamilton theorem, $A^2 = 0$ i.e. $A$ is nilpotent.

Else $X^2-$ tr$(A)X = X(X- $tr $(A))$ has distinct simple roots and vanishes $A$, hence $A$ is diagonalizable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.