A digression around Linear Algebra
Over the holidays I undertook to revisit my knowledge of linear algebra. I'd been talking with a friend, a college professor, and we discovered that neither of us felt we really understood the subject. We'd both studied it but we both felt that pure math majors had attained some grasp of the subject that we somehow missed while pursuing our more applied tracks. We decided to grab some MIT OpenCourseWare and see what we could do about rectifying this state of affairs.
We ended up with Gilbert Strang's Introduction to Linear Algebra. Likely we could have done with a more advanced text, but I personally felt my knowledge of the subject suffered in part from jumping too quickly into the advanced matter without having paid my dues of late nights solving factorizations and row reductions by hand. Correspondingly, I commited myself to working every exercise in the book from start to finish, skipping only those which were poorly-posed or obviously trivial. This has led to slow progress, but at least I won't be left with a feeling that I'd left any portion of the subject untouched!
As is characteristic of MIT texts, Strang excels at posing review problems that presage later material. This is among the reasons that working the problems from start to finish can be so fruitful. Indeed, after a month spent pounding rote matrix arithmetic and coming to an appreciation of the subject in the most wholesome Weberian way possible, I got as far as the following exercise (Strang 2.5 exercise 21):
There are sixteen 2 by 2 matricies whose entries are 1's and 0's. How many of them are invertible?
Now that sounds like an interesting problem! The preceding chapter gives us a good idea what the matrix inverse means in itself and in relation to singularness of the matrix, but we haven't encountered any higher-level concepts that might answer this question more simply or insightfully than attacking it by brute force. There are probably things discussed in later chapers -- spans and nullities or something like that, concepts specific to the subject and of which we're therefore admittedly ignorant -- in light of which this question becomes trivial. Being in ignorance of those for now, let's apply brute force methods and some basic knowledge of algebraic structures to see what insight obtains.
Brute-forcing the solution
To begin with, the exercise states on faith that our problem space comprises 16 matrices. Do we know that number is correct? Let's write our matricies in the form
with \(a\), \(b\), \(c\), and \(d\) each taking on one of the values \([0, 1]\). This leads to \(2^4 = 16\) possiblities, the indicated number.
Again, we suspect there's some common property among the subset of these that are invertible, but that begs the question. We'll think through what these may be in a moment, but first let's try the brute force approach. 16 isn't many cases to try, especially with a computer's help.
We know of a matrix of the above form that it's invertible iff \(ad-bc \neq 0\). It's easy enough to enumerate the possible combinations and count:
λ: isSingular (a, b, c, d) = a*d - b*c == 0
λ: let s = [0, 1]
λ: let searchSpace = [(a, b, c, d) | a <- s, b <- s, c <- s, d <- s]
λ: length searchSpace
16
λ: length $ filter (not . isSingular) searchSpace
6
We see that indeed we're looking at 16 matricies and that, of these, 6 are nonsingular. This figure is all the exercise asked for, but we'd expect there's some structure of interest regarding exactly which six of the sixteen have this property. We could display the results of the filter instead of counting them, but let's see if we can reason through what they may be instead.
Reasoning the solution
The problem of finding which six matrices fit our criterion is that of finding a particular subset of the 16 candidates. Since each cadidate is either included or excluded from a given subset, there are \(2^{16} = 65536\) subsets possible.1 With the blessing of foresight, we know we're only interested in those subsets having cardinality 6. There are \(_{16}C_{6} = 8008\) of these: we're looking for exactly one, and don't currently know of any meaningful higher-level concepts to guide us. This idea of cardinality is an interesting one, though. Not having any better ideas, let's define \(N=a+b+c+d\), the number of nonzero elements in each matrix, and see if that helps us break down the problem.
There's one matrix with \(N=0\), which is clearly singular. There's also one matrix for \(N=4\), which is also singular. Any matrix with \(N=1\) is going to be singular, by virtue of necessarily having a zero row.2 There are four such matrices. The \(N=2\) case is the most interesting: two of these six matrices have a zero row and are thus singular, likewise the two having a zero column. The other two matrices (the \(2\times2\) identity \(I_2\) and the \(2\times2\) exchange matrix \(J_2\)) are invertible. Finally, there are four \(N=3\) matrices (distinguished by the position of the single zero element), and each is nonsingular. This brings our total to the desired 6.
We've thus answered the question left open in the previous section, and we know which six matricies satisfy our criterion, and have some sense of their underlying structure. As before, we may be satisfied, but let's look deeper into what algebraic structure(s) that might evidence from taking these together.
Investigating further
Under matrix multiplication, it's clear that any identity matrix \(I\) forms the trivial group, and that \(\{I_2, J_2\} \cong \mathbf{Z_2}\). Let us define \(B_a\) as the (\(N=3\)) matrix having \(a=0\) (\(b=c=d=1\)), and \(B_b\), \(B_c\), and \(B_d\) analogously. We see that any one of these along with \(J_2\) serves to generate the others:
Prelude> import Data.Matrix
Prelude Data.Matrix> let i = identity 2
Prelude Data.Matrix> let j = permMatrix 2 1 2
Prelude Data.Matrix> let ba = fromLists [[0,1],[1,1]]
Prelude Data.Matrix> ba
┌ ┐
│ 0 1 │
│ 1 1 │
└ ┘
Prelude Data.Matrix> let bb = ba*j
Prelude Data.Matrix> bb
┌ ┐
│ 1 0 │
│ 1 1 │
└ ┘
Prelude Data.Matrix> let bc = j*ba
Prelude Data.Matrix> bc
┌ ┐
│ 1 1 │
│ 0 1 │
└ ┘
Prelude Data.Matrix> let bd = j*ba*j
Prelude Data.Matrix> bd
┌ ┐
│ 1 1 │
│ 1 0 │
└ ┘
This is starting to look like an interesting algebraic structure, but note that we don't have closedness:
Prelude Data.Matrix> ba*ba
┌ ┐
│ 1 1 │
│ 1 2 │
└ ┘
Prelude Data.Matrix> ba*bb
┌ ┐
│ 1 1 │
│ 2 1 │
└ ┘
Prelude Data.Matrix> ba*bc
┌ ┐
│ 0 1 │
│ 1 2 │
└ ┘
Prelude Data.Matrix> ba*bd
┌ ┐
│ 1 0 │
│ 2 1 │
└ ┘
Nor do we have the inverses (which we'd already have encountered otherwise). Let's calculate those:
Prelude Data.Matrix> inverse ba
Right ┌ ┐
│ -1.0 1.0 │
│ 1.0 0.0 │
└ ┘
ghci has muddied that up a little for us with the Either and converting our elements to Fractional, but it's clearly \([[-1,1],[1,0]]\), as we can verify. Since we know the other \(B_{\mu}\)'s (\(\mu \in \{a, b, c, d\}\)) can be generated by left- and right- multiplication by \(J_2\) and since \(J_2^\intercal=J_2\), we know we can find the other inverses likewise.
This explains why we haven't encountered the inverses: the elements of any member of our monoid \(\mathbf{\{I_2, J_2, B_\mu\}}\) are nonnegitive. What would happen if we were to allow -1 as a value, in addition to 0 and 1? This increases the problem space from 16 matrices to \(3^4=81\), of which we know at least 10, but no more than 71 to be invertible. We can find the actual number by a slight modification of our first snippet:
Prelude Data.Matrix> let s = [-1..1]
Prelude Data.Matrix> length $ filter (not . isSingular) [(a, b, c, d) | a <- s, b <- s, c <- s, d <- s]
48
That's more than I might have thought! It's curious that \(16/27\ \ (\approx 0.593)\) of the \([-1,0,1]\) matricies are invertible compared to only \(3/8\ \ (=0.375)\) of the \([0,1]\)'s. One must wonder what that function is like for other sets of integers. It's about time to put a bow on this blog post, but there are some other questions that seem to me obvious from this line of inquiry:
Of the 38 "new" invertible matrices, which, if any, are generated from our initial set \(\mathbf{\{I_2, J_2, B_\mu\, B_\mu^{-1}\}}\)?
What other characteristics lead to this determination? Does this reasoning extend to other invertible matricies with integral entries?
What about the \(3\times3\) case, the \(4\times4\) case, and on up? It was cool running into \(\mathbf{Z_2}\), even if that's a somewhat degenerate structure. We'd expect the permutation matrices to form group structures in higher-dimensioned matricies, but are there others? Checking \(2^n\) matrices gets prohibitive very quickly, even if those checks themselves were \(\mathcal{O}(1)\) (which, in point of fact, they're very much not). What deeper relationships exist to help us out?
Conclusion
Strang is very explicit in his preface that the book is to be used as I am using it: that exercises are meant to fill a dual role of providing practice while anticipating and foreshadowing concepts to come. I find this characteristic of MIT OpenCourseWare: that the pedagogy makes even lower-division undergraduate materials exciting and challenging, even in fields in which I feel myself relatively accomplished. This speaks (unsurprisingly) highly of the quality of the institution and the faith they're able to place in their undergraduates.
So, on the one hand, it's cool to be able to jump into a simple-but-interesting problem like this and run it to some conclusion. On the other, I can't help feeling a bit foolish, like the answers to the questions I'm inventing would be answered if I'd just pressed on with the next chapter or two instead of digressing down this tack.
Back to the first hand, we have shown something in the way of how useful the tools of Modern Algebra are at investigating different domains, even if Linear Algebra is customarily taught first.