An upper triangular matrix is invertible if and only if all of its diagonal-elements are non zero (Again)

An upper triangular matrix is invertible if and only if all of its diagonal-elements are non zero.

This is an fundamental proposition in linear algebra, and I expect it appears in the problem sets of most introductionary courses. I've provided a more formal proof of this before, but I'd like here to present a more intuitive proof. If you prefer to read the PDF download it here.

First of all, note that by being upper triangular, an assumption is that the matrix is square. Slightly more involved, but similar reasoning can be applied to rectangular upper-trapezoidal matrices, but this need not concern us now.

A matrix TeX Embedding failed! is said to be invertible if there exists a matrix TeX Embedding failed! such that TeX Embedding failed! where TeX Embedding failed! is the identity matrix. The existence of TeX Embedding failed!, allows equations of the form TeX Embedding failed! to be solved for the solution vector TeX Embedding failed! for any target vector TeX Embedding failed!, by observing that:

TeX Embedding failed!

It turns out that the invertibility of TeX Embedding failed! is actually equivalent to saying that a solution vector TeX Embedding failed! exists for any target vector TeX Embedding failed! in the equation TeX Embedding failed!. Thus the object of this proof is to demonstrate, given an TeX Embedding failed! square matrix TeX Embedding failed!, that there exists a solution vector TeX Embedding failed! for all target vectors TeX Embedding failed!, if and only if all the diagonal elements of the matrix TeX Embedding failed! are non-zero. The condition to be satisfied is:

TeX Embedding failed!

Let the elements of TeX Embedding failed!, TeX Embedding failed!, and TeX Embedding failed! be referenced as follows:

TeX Embedding failed!

And let TeX Embedding failed!, TeX Embedding failed!, TeX Embedding failed! represent the columns of the matrix TeX Embedding failed!.

The if part of the proposition requires demonstrating that a solution vector TeX Embedding failed! can be constructed for any target vector TeX Embedding failed!. The only if part requires demonstrating that this task is impossible if any of the diagonal elements are zero. I intend to prove both parts symultaneously, and directly.

The term TeX Embedding failed! can be written

TeX Embedding failed!

This says that TeX Embedding failed! is a linear combination of the columns of TeX Embedding failed!, with coefficients taken from TeX Embedding failed!. Now, let us proceed to construct the solution vector TeX Embedding failed! for some given TeX Embedding failed!.

Let us start with the target TeX Embedding failed!, the last element of TeX Embedding failed!. This must arise from some linear combination of the TeX Embedding failed!th rows of columns TeX Embedding failed! to TeX Embedding failed!, but since TeX Embedding failed! is upper-triangular, the columns TeX Embedding failed! all contain a zero in the TeX Embedding failed!th row, that is the elements TeX Embedding failed! are all zero. This means that only the TeX Embedding failed!th column has any influence in determining the element TeX Embedding failed!, in particular the product TeX Embedding failed! determines the result. From this it follows that TeX Embedding failed! cannot be zero, for if it is zero, then TeX Embedding failed! must also be zero. And if TeX Embedding failed! is zero, then it is impossible to find an TeX Embedding failed! for if TeX Embedding failed! whenever TeX Embedding failed!. Thus TeX Embedding failed! is not zero.

Since TeX Embedding failed! is not zero, it analytically follows that TeX Embedding failed! for any target TeX Embedding failed!. Thus the element TeX Embedding failed! in the vector TeX Embedding failed! has been correctly established. Furthermore, this is the only way the result can be obtained, since no other column holds any influence over the result, therefore the coefficient TeX Embedding failed! is also uniquely determined.

Now consider the next element up in the target vector TeX Embedding failed!, this must arise from some linear combination of the TeX Embedding failed!th rows of the columns TeX Embedding failed! to TeX Embedding failed!, but from the previous analysis, we observe that the coefficient of the last column TeX Embedding failed! has already been established as TeX Embedding failed!, therefore the TeX Embedding failed!th column contributes a known quantity, TeX Embedding failed!, to the linear combination. Furthermore, since the matrix TeX Embedding failed! is upper triangular, every column to the left of TeX Embedding failed!, contains a zero in the TeX Embedding failed!th row. That is, the elements TeX Embedding failed! to TeX Embedding failed! are all zero. Thus the only column that can change the result TeX Embedding failed! is the TeX Embedding failed!th column, and it can only do so via the coefficient TeX Embedding failed!. The result is thus determined as follows: TeX Embedding failed!. Now, since TeX Embedding failed! is known, it follows that TeX Embedding failed! cannot be zero otherwise the only possible result is TeX Embedding failed! which is contrary to the requirement that TeX Embedding failed! can be found for any TeX Embedding failed!. Therefore TeX Embedding failed! is not zero and TeX Embedding failed!. Thus the value TeX Embedding failed! has been correctly established.

The construction proceeds in this manner with the next target TeX Embedding failed!, and the reasoning is the same. Since the coefficients for the columns to the right of TeX Embedding failed! have already been uniquely determined, and since the columns to the left all contain zero in the TeX Embedding failed!th row, it follows that the product of the diagonal element TeX Embedding failed! and the coefficient TeX Embedding failed! is the only way to change the target TeX Embedding failed!. Which means that TeX Embedding failed! cannot be zero, and the coefficient TeX Embedding failed! is analytically determined as follows: TeX Embedding failed!.

This process continues with the remaining elements of the vector TeX Embedding failed!, in order of decreasing row index, until all the coefficients TeX Embedding failed! have been established.

Note, in general, the target TeX Embedding failed! has zeros in TeX Embedding failed!th row of the columns TeX Embedding failed! to the left of TeX Embedding failed!, and the contributions of the columns to its right TeX Embedding failed! are uniquely determined by the coefficients TeX Embedding failed!. Therefore TeX Embedding failed! can't be zero, otherwise the result is uniquely determined when it is required that any result can be produced. TeX Embedding failed! is computed as TeX Embedding failed!. The latter always takes the same form, and is simply the target TeX Embedding failed! minus the known contributions that the columns to the right of TeX Embedding failed! will make, divided by TeX Embedding failed! itself. To see why this works, when the linear combination of the columns are taken, the TeX Embedding failed!th column will contribute TeX Embedding failed! which evaluates to TeX Embedding failed! but this right hand sum, is simply the contributions that the columns to the right of TeX Embedding failed! will contribute, and so we have TeX Embedding failed! which obviously evaluates to TeX Embedding failed!, giving the required result.

Therefore we have shown a way to construct the solution vector TeX Embedding failed! for any target vector TeX Embedding failed! given an upper triangular matrix TeX Embedding failed! with non-zero diagonal elements, and have shown that this construction is only possible if all the diagonal elements are non-zero. Q.E.D

Batteries are ridiculously crap

In the absence of advances in fusion energy, one of the most important technological outcomes of the next decade will be improvements in battery technology.

Battery technology has advanced at a snails pace compared to other kinds of technology. The basic lead-acid battery has an energy density between 30-40 Wh/kg whereas the best commercially available lithium ion batteries have energy densities between 100 and 250 Wh/kg. So being generous, let's say that battery energy densities have improved by a factor of 10.

Now consider other techological domains. Let's take CPU speed. To try and be fair, let's ignore really old machines like the Z1 with its 1Hz clock speed and take the 1982 Commodore 64 as a good example of a commercially popular system. The C64 had a clock speed of around 1Mhz. Whereas these days 3Ghz CPUs are common. That gives at least a factor 3000 improvement. But really, the improvements are much greater. If one considers that the AMD 6174 processor has 12 cores running at 2.2Ghz, this is something like an increase in processing power of 25000 for a single chip. Our servers at work have 4 of these beasts on one motherboard, which means that a single commercially available computer has 100,000 times the processing power.

How about RAM? Again taking the C64, it had 64kB RAM (obviously). Now 12GB in a home desktop is quite common these days: a factor 187500 increase in capacity. Considering individual modules, samsung make a 32GB DIMM, which is larger by the C64 by a factor of 1/2 million. Going bigger, server machines such as the Dell PowerEdge R910 can take 1TB of RAM, which is over 15 million times larger than the C64. Obviously there are some huge machines out there on the Top 500, but keeping things within reason we can say that RAM capacity improvements are at least a factor of a million.

And what about fixed storage? The 1980 Seagate Technology ST506 5.25 inch HD had a capacity of 5MB. These days single unit 3TB hard drives are available. So without needing to talk of specialist hardware, or to go back to even older hard drives, the capacity improvement easily hits a factor of a billion.

So processing power has improved by a factor of 100,000, RAM a factor of a million, and fixed storage a factor of a billion. Comparably, the increase in the energy density of batteries of x10 seems laughable.

Clearly battery technology has been lagging behind somewhat. The advent of high capacity, affordable batteries, with quick charging times would enable the green revolution to take hold. Electric cars and distributed storage are obvious beneficiaries. But simply being able to use a laptop for more than a few hours would be great too, imagine a laptop battery that lasts a week or more, wouldn't that be fantastic?

I don't want to go into future battery technologies, because I don't have time, but Graphene seems to be the hot material right now, and Graphene based super-capacitors seem promising.

Mushroom Test

Hi, how's it going? Not bad I hope.

Last autumn I got obsessed with identifying, picking, and eating wild mushrooms. I was going to make a website about it, probably still will at some point, but until then, I just made a quick "Mushroom test" in Javascript. You can play it here:

http://www.mushroompictures.co.uk

Here is a screenshot:

Obviously don't go eating mushrooms based on what you learn from that game. Wait a sec, I'm not one to tell people what to do, go ahead if you want, but don't blame me if you end up dead or on dialysis.

Fugglers

My girlfriend's sister has started making stuffed felt toys. Perhaps they are your thing?

This is what she has to say:

It's been said that I need a hobby. Here it is. The moral of this story? Be careful what you wish for. My house is filled with these creatures now, and my husband has a sadness about it all. Sometimes he writes a diary, but when I look all the pages are blank, except for small drawings of snails wearing moustaches and looks of disdain. Why? Why, he demands. Why must these creatures chew my sanity so? Banish them from our property, dear wife. I implore you. NO GOOD WILL COME OF THIS.

I've called them Fugglers. You may call me Mrs McGettrick.

Hand made with loving care, and a fistful of false teeth, every one of Mrs McGettrick's Fugglers is unique.

SMALL PRINT: Mrs McGettrick's Fugglers are not suitable for small/medium/oral fixated children, as there is a risk that small parts could come loose and present a choking hazard. Colours may vary from the photographs, due to monitor settings, flash, and my inability to use a camera. Mrs McGettrick's Fugglers are made in a house containing a cat. A cat who pulls out her own fur in an attempt at shocking nudity, and who walks like Nosferatu. If you have cat allergies, I might suggest you avoid buying from this shop. Mrs McGettrick's Fugglers are not suitable for people who don't appreciate cuddly toys with uncannily realistic teeth jutting out from their mouths. Mrs McGettrick's Fugglers are not suitable for people who have ever harboured a suspicion that toys can come alive at night.

Here is the link to her shop:

http://www.etsy.com/shop/cathairandteeth

Man Flu

I had the flu last week. How do I know it was the flu and not a cold? Well I don't know for sure but fever came on extremely quickly and I was bedridden for 3 days with terrible chills and dehydration. It took a week of being zonked to dissappear, and I still look a little off-color.

Once upon a time I told a woman that I had flu and she exclaimed "What, man flu!" in a mocking and sexist manner implying that I only had a cold but was being a cry baby, and that men in general are in habit of doing this.

Well I wanted to get to the bottom of this man-flu nonsense, so I looked up a paper about the symptoms of cold and flu [1]. Here are some pertinent excerpts from the most cited journal paper on the matter:


The clinical expression of URTIs is variable and is partly influenced by the nature of the infecting virus but to a greater extent is modulated by the age, physiological state, and immunological experience of the host. Depending on these factors, URTIs may occur without symptoms, may kill, or most commonly will be associated with an acute self-limiting illness.


“Common cold” and “flu” are syndromes of familiar symptoms caused by viral infection of the upper respiratory tract. It is difficult to define the syndromes exactly because of great variation in the severity, duration, and types of symptom. Rhinoviruses account for 30–50% of all colds, and coronaviruses are the second most common agent, accounting for 10–15% of colds. Influenza viruses account for 5–15% of colds, and cold viruses such as respiratory syncytial virus are responsible for much flu-like illness, demonstrating that there is much overlap in aetiology and symptomatology of common cold and flu syndromes.

So you can shove your man flu up your arse! You haven't got a clue what virus I'm infected with. In practice neither do I, but I think I'm in a better position than you to judge my own symptoms relative to prior infections and hazard a guess.


The best predictors for influenza are cough and fever, since this combination of symptoms has been shown to have a positive predictive value of around 80% in differentiating influenza from a population suffering from flu-like symptoms.

Yes so I think I had flu and not a cold. So my man flu friend, it would appear you don't have telepathic medical abilities afterall and are in fact a sexist chump. The paper has some other interesting things to say:


Fever in response to infection is found in a wide range of animals and is believed to be beneficial as regards the host response to infection. Fever is usually associated with novel or severe viral infections, especially emerging viral infections where the virus is novel to the host, as in influenza epidemics and SARS. As discussed, fever is uncommon in adult cases of common cold, but is common in infant cases, presumably because the adult has been exposed to numerous common cold viruses and subsequent infections do not trigger a strong immune response, whereas the viruses are novel to the infant.

Hmm, so that thing I had last week was probably something I hadn't had before. And also, man flu freak, if your baby has a fever it might be "just" a cold. Bet you didn't expect that did you? Bet you didn't expect that not even the converse of you're stupid man flu attack can be considered true? lol OK finally, I like one of the conclusions:


The unpleasant symptoms of fever, malaise, and anorexia help to overcome infection and it is debatable whether elimination of these symptoms with non-steroidal anti-inflammatory drugs is beneficial. At present there is no evidence that symptomatic treatment of URTIs interferes with the course of the common cold or influenza but this is an area that is worthy of more research.

So perhaps the next time I catch a Rhinovirus, coronoavirus, Influenza virus, or similar, perhaps I won't bother taking any medicine and see how it works out.

[1] "Understanding the symptoms of the common cold and influenza" Ron Eccles, Lancet Infect Dis 2005;
5: 718–725 http://140.116.58.126:8080/%E5%85%92%E7%A7%91/Feb-27.pdf

It is absurd to label Jullian Assange a hypocrite

I'd like to argue against a ridiculous notion that has irked me on a few occasions recently with regard to Wikileaks and Julian Assange. A poll on the Daily Mail site asks "Does Julian Assange have a right to privacy?". And the Telegraph asks us "Is Julian Assange a coward or a hypocrite?" I cite these papers since their readerships are particularly docile, but there are many other examples of this deliberate juxtaposition of state and personal privacy in the media of late.

The position seems to be that for free speech to be considered just and right, it must result in the forfeit of personal privacy. Since exercising the former without incurring the latter is considered "hypocritical" and therefore a bad thing. How preposterous!

In lay-mans terms this is what certain elements of the media expect or want us to think: "Assange has exposed these private secrets so he's clearly a hypocrite if he tries to protect his own secrets, especially considering the magnitude of the secrets that he has exposed.".

The strategy is to make people believe that personal and state privacy are commensurate things, in order that an individual's strong feelings concerning the former are confused with the latter. In the ideal case this should result in a perverse viewpoint and a desire to protect the latter. This is quite a clever strategy.

Corporations and governments however, should not be prescribed the same rights, privacy or otherwise, as persons. And I implore those that side with the outlined position to see it for what it really is: propaganda that is harmful to individual freedoms.

CUPs on FreeBSD: "lpr: lp: unknown printer"

I don't have time for historical prejudices so for printing on FreeBSD so I use CUPS.

The CUPS port installs its own lpr and lp and probably some other binaries in /usr/local/bin/. This causes jobs not to print because /usr/bin/lpr and /usr/bin/lp do not work with cups. A quick and dirty solution is to do this as root:

cd /usr/bin
mv lpr lpr-old
mv lp lp-old

Then it should work. There might be some other binaries that need doing but I've not seen any other errors.

sand and shells

send the monsters in
mutant fairytales
gaping mouths with silver teeth
trawling for souls

tear the place up
and spit out the bones
bury them
and hope the dogs don't find them

The Conker Deal

As autumn approaches, every young boy of Conker age, keeps a watchful eye on the growing fruits of his favourite horse chestnut trees. And it is common, especially among the eager, to prematurely harvest the crop before somebody else does.

Harvest usually takes place on a nice sunny autumn afternoon, blue skies and a cool fragrant breeze, nothing more. The harvest is affected by means of climbing, which turns blue jeans to green jeans, branch shaking, and surface-to-tree stick-throwing. The whole affair is almost religious in its dedication and annual recurrance.

The harvested conkers, split prematurely from their bright green spikey shells under foot on the nearby roads, are white in appearance, and take several days in the airing cupboard to reach the colour of their naturally ripened and de-shelled brethren. The roads around the scene are left littered with browned decaying half-shells, and a few dead conkers, the latter having been smashed into oblivion during the de-shelling through accidentally over forceful stamping. The victim trees are left battered, bearing an inevitable few missing branches, with giant fingered leaves leaves scattered everywhere.

It is during the harvest that our story begins. I remember one particular year, up near Toft Hill, a friend and and I happened upon a row of conker trees next to the busy Southam road. Being on the periphery of the village, these were unmolested by our rivals.

The trees were parallel to the road, squeezed between the pavement, some bushes, and an adjacent field which had horses in it. We were able to break through the bushes and into the secluded haven nestled safely under the bows of the trees.

These particular conkers, were odd, in that some of them had smooth shells that took on a colour that was more olive than the bright green of their pointed neighbors. Nethertheless, these trees had some real monsters on them. Shells that were bigger than our fists!

The thing with giant conker shells, is that they typically turn out to have multiple conker seeds inside. Doubles perhaps being the most common, followed by triples, singles, and sometimes even quads. More conkers per shell however, usually results in smaller conker seeds. So the desire when a monster shell is spotted, is that it contains only one or two monster seeds, and when this rings true, a boy can know no comparable pleasure.



Image Copyright: Andrew Dunn

Anyway, to get back to the point of the story. My friend Richard and I spent the Saturday afternoon collecting conkers from the grove, and we amassed a bucket full at least. For some reason we got the idea that we had collected 500 conkers, although we never counted them.

Richard, being the enterprising type, came up with the idea that we should try and sell the conkers at our middle school on the coming Monday, and I agreed. It was clear that we had far more conkers than we could possibly use ourselves. Richard decided that for 500 conkers, a fair price would be £5, a penny per conker. £5 was a lot to me, my weekly pocket money at the time being 40p. The sale would net us each £2.50, more than 6 weeks of pocket money!

When Monday came, I packed the conkers into a blue rucksack, struggled to zip up its bulging contents, and headed off to school in good spirits.

Richard was quick off the mark and as morning break came around he went straight over to his buyer. A farmer type guy known as Brandle. It was apparent that he already had Brandle in mind, and I could tell from his approach that he was able to play this guy like a true salesman.

Richard worked his magic, and after a few minutes, had Brandle willing to hand over £5 for the "500" conkers. Brandle looked excited, and clearly considered it a great deal. At this point the morning break ended and we went back inside.

During the interim work period, before lunch break, in a feat of salesmanship as conniving as it was brilliant, Richard came up with a scheme to double the profits.

I was to approach Brandle and make the claim that Richard himself, having been the broker for the deal, had decided that in fact he wanted the conkers for himself, and was willing to offer me £7. For now it seemed I had become the "owner" of the conkers.

I warned Richard that this might be pushing it too far, that we should be grateful for £5, and I tried to talk him out of it. But he was my best friend at the time, and so eventually I agreed to it.

So, when lunchbreak arrived, I approached Brandle before he went outside, and set about explaining the situation. I explained as best I could how Richard, having had a close look at the Conkers, was now interested in them himself, and I told Brandle that if he really wanted them, he would have to pay £10. Richard was watching eagerly over my shoulder all the while.

At first Brandle seemed to respond positively to the proposal, but then Richard started playing up the role of "interested buyer" a bit too enthusiastically, and ultimately perverted it by symultaneously giving the hard sell in encouraging Brandle to take the deal. And so, as quickly as the original deal had been setup, and as quickly as it had instilled me with the warm belief that I'd soon be the owner of a nice £2.50, the deal toppled and crashed upon the floor. It was wrecked. Brandle had backed out of the deal, having been pushed to the point where his senses came back, and the allure of "500" shiny conkers was lost.

Dispondently, I furrowed my brow and started thinking. After a couple of seconds and an idea flashed into my head. There was only one thing for it. I knew exactly what to do. Excitedly, I took my rucksack and rushed over to the bottom playground. It was already populated, since we had spent several minutes presiding over the deal inside.

I went to the top of the steps which overlooked the playground, unzipped the bag and shouted, as loud and protracted as I could:

"S..C..R..A..M..B..L..E!"

whilst tipping the conkers out of the bag. As they bounced noisily down the steps and onto the grey asphalt, children were already running over, having heard the celebrated and familiar call of scramble and were rushing to collect as many conkers as possible.

"Ashley!" came a commanding shout from behind me "What the hell are you doing! Pick those up at once!" bellowed the on-duty teacher. Sheepishly I said "OK" and felt a little bit worried, but as I looked up my worries evaporated, a smile cracked across my face. There was no longer any need. The conkers were already gone!

The Kensington Orbit Optical Trackball is a Better Trackball than the Logitech Marble Mouse

A while ago I was banging on about my new trackball, the Logitech Marble Mouse:

Well, not long after, I also bough the Kensington Orbit Optical Trackball for a different location:

BTW the latter has a rubber extender that makes it longer so as to provide more palm support.

Well, I want to tell you that the latter trackball is better. Mainly because it has a scrollwheel (that is a dream to use btw). After using the Kensington for a while and then switching to the Logitech, my mind was screaming for the scrollwheel.

The Logitech is still way better than a smartphone, an incredible experience!! (I couldn't resist: Star Wars I-Pad Briefing). No really, the Logitech is still better than a mouse because of the RSI thing, but you have to get used to either using PgDn and PgUp or using the scroll bar for scrolling.

With the Kensington, the scrollwheel is totally natural and just makes it great to use. I think the logitech shape might be slightly more comfortable, but overall the scrollwheel pushes the Kensington into the lead by quite a bit IMO.

NOTE: There is a program: http://simans.net/marble/, which can be used to simulate scrolling on the Marbleman. I've tried using it, and although it works, I wasn't able to keep the habit, and sometimes pressed the wrong button by accident, thus I went back to manually scrolling instead.

A final point I should make, which has only come to light recently (I'm editing this on 12/03/2011), about 6 months after purchasing the Kensington trackball, is that the right click button sticks every now and again. By this I don't mean that it sticks down, but it is a little bit harder to press than normal, as if it isn't quite sitting right in its seat. And playing a little with the button right now I can see that my button has gone a little loose so I think that this is responsible. Once clicked it goes back to normal. But it is a little annoying that this problem has manifested. It could be just the way I click it, I don't know. I'd still recommend the trackball, because its the best out there I've tried, but I'm an honest guy so I thought you should know.

I've added some amazon links below, which I get a commission on. I thought long and hard about whether or not I should add links because it might be seen that I'm explicitly trying to sell something, rather than linking to something I wanted to talk about anyway, which could bias my perceived integrity. i.e, perhaps I'm bullshitting about the product because I want loads of people to click on it? And I could be, you'll just have to decide for yourself. Let me know if you think this threatens my integrity, and if I get enough concern, I'll remove these links.

[amazon B002Q42S4E full] [amazon B002Q42S4E lowestpriceformattedprice]
[amazon B001DQY9AW full] [amazon B001DQY9AW lowestpriceformattedprice]
Syndicate content