IMO 2016 Diary – Part One

Posted on July 12, 2016 by dominicyeo

Friday 1st July

It’s my last morning as an Oxford resident, and I have to finish the final chapter of my thesis, move out of my flat, print twenty-four boarding passes, and hurtle round town collecting all the college and department stamps on my pre-submission form 3.03 like a Pokemon enthusiast. Getting to Heathrow in time for an early evening flight seems very relaxed by comparison, even with the requirement to transport two boxes of IMO uniform. Because I wasn’t paying very much attention when I signed off the order, this year we will be wearing ‘gold’, but ‘lurid yellow’ might be a better description. Hopefully the contestants might have acquired some genuinely gold items by the time we return to this airport in two weeks.

Saturday 2nd July

Our flight passes rapidly. I proved an unusual function was locally Lipschitz, watched a film, and slept for a while. Others did not sleep at all, though I suspect they also did not prove any functions were locally Lipschitz. The airport in Hong Kong is truly enormous; for once the signs advertising the time to allow to get to each gate have a tinge of accuracy. We have plenty of time though, and there is substantial enthusiasm for coffee as we transfer. Cathay Pacific approach me with a feedback form, which turns out to include 130 detailed questions, including one concerning the ‘grooming’ of the check-in staff, while we all collectively tackle an inequality from the students’ final sheet of preparatory problems.

Before long though, we have arrived in Manila, where Jacob is uncontrollably excited to receive a second stamp in his passport, to complement his first from Albania at the Balkan Olympiad last month. As we bypass the city, we get a clear view of the skyscrapers shrouded in smog across the bay, though the notorious Manila traffic is not in evidence today. We pass through the hill country of Luzon Island, the largest of the Philippines and get caught in a ferocious but brief rainstorm, and finally a weekend jam on the lakeside approach to Tagaytay, but despite these delays, the fiendish inequality remains unsolved. I’m dangerously awake, but most of the students look ready to keel over, so we find our rooms, then the controls for the air conditioning, then let them do just that.

Sunday 3rd July

We have a day to recover our poise, so we take advantage of morning, before the daily rain sets in, to explore the area. We’ve come to Tagaytay because it’s high and cool by Philippine standards, so more conducive to long sessions of mathematics than sweltering Manila. We follow the winding road down the ridge to the shore of Taal Lake, where a strange flotilla of boats is docked, each resembling something between a gondola and a catamaran, waiting to ferry us to Taal Volcano, which lies in the centre of the lake. The principal mode of ascent from the beach is on horseback, but first one has to navigate the thronging hordes of vendors. Lawrence repeatedly and politely says no, but nonetheless ends up acquiring cowboy hats for all the students for about the price of a croissant in Oxford.

Many of us opt to make the final climb to the crater rim on foot, which means we can see the sulphurous volcanic steam rising through the ground beside the trail. From the lip we can see the bright green lake which lies in the middle of the volcano, which is itself in the middle of this lake in the middle of Luzon island. To the excitement of everyone who likes fractals, it turns out there is a further island within the crater lake, but we do not investigate whether this nesting property can be extended further. After returning across the outer lake, we enjoy the uphill journey back to Tagaytay as it includes a detour for a huge platter of squid, though the van’s clutch seems less thrilled. Either way, we end up with a dramatic view of an electrical storm, before our return to the hotel to await the arrival of the Australians.

Monday 4th July

Morning brings the opportunity to meet properly the Australian team and their leaders Andrew, Mike and Jo. We’ve gathered in the Philippines to talk about maths, and sit some practice exams recreating the style of the IMO. The first of these takes place this morning, in which the students have 4.5 hours to address three problems, drawn from those shortlisted but unused for last year’s competition.

After fielding a couple of queries, I go for a walk with Jo to the village halfway down the ridge. On the way down, the locals’ glances suggest they think we are eccentric, while on the ascent they think we are insane. About one in every three vehicles is a ‘jeepney’, which is constructed by taking a jeep, extending it horizontally to include a pair of benches in the back, covering with chrome cladding, and accessorising the entire surface in the style of an American diner. We return to find that the hotel thinks they are obliged to provide a mid-exam ‘snack’, and today’s instalment is pasta in a cream sauce with salad, served in individual portions under cloches. Andrew and I try to suggest some more appropriate options, but we’re unsure that the message has got across.

I spend the afternoon marking, and the UK have started well, with reliable geometry (it appears to be an extra axiom of Euclid that all geometry problems proposed in 2015/2016 must include a parallelogram…) and a couple of solutions to the challenging number theory problem N6, including another 21/21 for Joe. Part of the goal of this training camp is to learn or revise key strategies for writing up solutions in an intelligible fashion. At the IMO, the students’ work will be read by coordinators who have to study many scripts in many languages, and so clear logical structure and presentation is a massive advantage. The discussion of the relative merits of claims and lemmas continues over dinner, where Warren struggles to convince his teammates of the virtues of bone marrow, a by-product of the regional speciality, bulalo soup.

Tuesday 5th July

The second exam happens, and further odd food appears. Problem two encourages solutions through the medium of the essay, which can prove dangerous to those who prefer writing to thinking. In particular, the patented ‘Agatha Christie strategy’ of explaining everything only right at the end is less thrilling in the realm of mathematics. It’s a long afternoon.

We organise a brief trip to the People’s Park in the Sky, based around Imelda Marcos’s abandoned mansion which sits at the apex of the ridge. In the canon of questionable olympiad excursions, this was right up there. There was no sign of the famous shoe collection. Indeed the former ‘palace’ was open to the elements, so the style was rather more derelicte than chic, perfect for completing your I-Spy book of lichen, rust and broken spiral staircases. Furthermore after a brief storm, the clouds have descended, so the view is reminiscent of our first attempt at Table Mountain in 2014, namely about five metres visibility. A drugged parrot flaps miserably through the gloom. Even the UK team shirts are dimmed.

There is a shrine on the far side of the palace, housing a piece of rock which apparently refused to be dynamited during the construction process, and whose residual scorchmarks resemble the Blessed Virgin Mary. A suggested prayer is written in Tagalog (and indeed in Comic Sans) but there is a man sitting on the crucial rock, and it’s not clear whether one has to pay him to move to expose the vision. Eventually it clears enough to get a tolerable set of team photos. Joe tries to increase the compositional possibilities by standing on a boulder, thus becoming ten times taller than the volcano, so we keep things coplanar for now. Harvey finds a giant stone pineapple inside whose hollow interior a large number of amorous messages have been penned. He adds

$\mathrm{Geoff }\heartsuit\,\triangle \mathrm{s}$

in homage to our leader, who has just arrived in Hong Kong to begin the process of setting this year’s IMO papers.

Balkan MO 2016 – UK Team Blog Part Two

Posted on May 11, 2016 by dominicyeo

This short blog records the UK team at the Balkan Mathematical Olympiad 2016, held in Albania. The first part is here. A more mathematical version of this report, with commentaries on the problems, will appear at the weekend.

Sunday 8th May

Gerry and I are separated by 15km, so we can’t work together until this morning, when I also get a chance to see the UK team at their base in Vore, before they are whisked off to a beach. We now have the chance to work on the geometry together, which includes two sensible trigonometric arguments, and a nice synthetic proof only with reference to an inverted diagram. We quickly decide that this isn’t a major error, and aim to schedule our meetings as quickly as possible.

The coordinators for questions 3 and 4 seem very relaxed, and we quickly get exactly what we deserve, plus a spurious extra point for Michael because he used the phrase ‘taxicab metric’ in his rough. Thomas’s trigonometry, especially its bold claim that ‘by geometry, there are no other solutions’ when an expression becomes non-invertible, seems not to have been read entirely critically. Michael’s inverted diagram is briefly a point of controversy, but we are able to get 9 rather than the 7 which was proposed, absurdly for an argument that was elegant and entirely valid in the correct diagram up to directed angles. Question 1 is again rapid, as the coordinators say that the standard of writing is so clear that they are happy to ignore two small omissions. It transpires after discussion with, among others, the Italian leader, that such generosity may have been extended to some totally incorrect solutions, but in the final analysis, everything was fair.

So we are all sorted around 11.30am with a team score of 152, a new high for the UK at this competition. This is not necessarily a meaningful or consistent metric, but with scores of {20,21,22,29,30,30} everyone has solved at least two problems, and the three marks lost were more a matter of luck than sloppiness. Irrespective of the colours of medals this generates, Gerry and I are very pleased. We find a table in the sun, and I return to my introduction while we await progress from the other countries’ coordinations, and our students’ return.

This does not happen rapidly, so I climb the hill behind the hotel up a narrow track. A small boy is standing around selling various animals. Apparently one buys rabbits by the bucket and puppies by the barrel in Albania. Many chickens cross the road, but key questions remain unanswered. From the summit, there is a panorama across the whole Tirana area, and the ring of mountains encircling us. One can also see flocks of swifts, which are very similar to swallows, only about twice as large, and their presence in any volume makes no comment on the arrival of the British summer.

The students return mid-afternoon, and are pleased with their scores. Jamie explains their protracted misadventure with a camp bed in their ‘suite’ of rooms, and Jacob shows off his recent acquisitions: a felt hat, and a t-shirt outlining the border of a ‘greater Albania’. The fact that they didn’t have his size seems not to have been a deterrent, but hopefully the snug fit will discourage him from sporting it in Montenegro, which might lead to a political incident.

Hours pass and time starts to hang heavily as dinner approaches, with no sign of the concluding jury meeting. Finally, we convene at 10pm to decide the boundaries. The chair of the jury reads the regulations, and implements them literally. There’s a clump of contestants with three full solutions, so the boundaries are unusually compressed at 17, 30 and 32. A shame for Thomas on 29, but these things happen, and three full solutions minus a treatment of the constant case for a polynomial is still something to be happy about. Overall, 4 bronze and 2 silvers is a pleasing UK spread, and only the second time we have earned a full set of medals at this competition. The leaders are rushed back to Tirana, but hopefully the teams have enough energy left for celebration!

Monday 9th May

Today is the tutti excursion, but on the way the leaders stop at the city hall to meet the mayor of Tirana. He is new to the office, reminiscent of a young Marlon Brando, and has a bone-crushing handshake. He improvises an eloquent address, and negotiates with flair the awkward silence which follows when the floor is opened for speeches in response. In the end, the Saudi leader and I both say some words of thanks on behalf of the guest nations, and soon we are back on our way south towards Greece. The Albanian motorway is smooth and modern, but we find ourselves competing for space with communist-era windowless buses and the occasional pedestrian leading by hand a single cow.

Our destination is Berat, known as the city of a thousand windows, and home to a hilltop castle complex from which none of the thousand windows are visible. The old orthodox cathedral is now a museum of icons and other religious art, and we get a remarkably interesting tour from a local guide. The highlight is a mosaic representation of the Julian calendar, and we discuss whether the symmetries built into the construction would be more conducive to a geometry or a combinatorics question.

Back in Tirana, we reconverge at the closing ceremony, held in the theatre at a local university for the arts. While we wait, there is a photo montage, featuring every possible Powerpoint transition effect, in which Jacob and his non-standard hat usage makes a cameo appearance. We are then treated to a speech by Joszef Pelikan, who wows the crowd by switching effortlessly into Albanian, and some highly accomplished dancing, featuring both classical ballet and traditional local styles.

The ministry have taken over some aspects of the organisation here, and there is mild chaos when it’s medal time. The leaders are called upon to dispense the prizes, though the UK is snubbed for alphabetic reasons. The end result is that forty students are on stage with neither medals nor any instructions to leave. Eventually it vaguely resolves, though it is a shame there is no recognition for the two contestants (from Serbia and Romania) who solved the final problem and thus achieved a hugely impressive perfect score.

As you can see, the UK team look extremely pleased with themselves, and Michael’s strategy to get to know all the other teams through the medium of the selfie is a storming success. A very large number of photographs are taken, and Thomas is not hiding in at least one of them. The closing dinner is back in Vore, which is very convivial and involves many stuffed vine leaves. Rosie suggests we retire somewhere quieter, but by the time we establish how to leave, she has instead dragged the rest of the team onto the dancefloor, where near-universal ignorance of the step pattern is no obstacle to enjoying the folk music. The DJ slowly transitions towards the more typical Year 11 disco playlist, and Jill feels ‘Hips don’t lie’ is a cue for the adults to leave.

Tuesday 10th May

Our flight leaves at 9pm so we have many hours to fill. It turns out that we have one of the shortest journeys. The Serbians have caught a bus at 3am, while the Cypriots are facing stopovers in Vienna and Paris! It is another beautiful day, so we hire a small van to take us to Lezhe, the hometown of our guide Sebastian, and the nearby beach at Shengjin.

We walk to the tip of the breakwater, and watch some fishermen hard at work, though apparently today is a lean catch. The buildings along the beachfront are a sequence of pastel colours, backing onto another sheer mountain, and we could easily be in Liguria. Jamie is revising for his A2-level physics and chemistry exams, which start at 9am tomorrow morning, and the rest of the team are trying to complete the shortlist of problems from IMO 2007. They progress through the questions in the sand, with a brief diversion as Jacob catches a crab in the shallows with his bare hands for no apparent reason.

After a fish-heavy lunch, we return to Vore, and I’ve run out of subsubsections to amend, so propose another walk into the hills. The animals we meet this time appear not to be for sale. Some scrabbling in the undergrowth is sadly not the longed-for bear or wolf. Many of its colleagues are loitering on the local saddle point, and our Albanian companion Elvis describes them as ‘sons of sheep’, while Renzhi confidently identifies them as cows. They are goats. There is a small but vigorous goatdog, who reacts with extreme displeasure to our attempt to climb to one viewpoint, so Gerry leads us off in another direction up the local version of the north face of the Eiger. We do emerge on the other side, dustier but with plenty of heavily silhouetted photographs.

Then the hour of departure, and time to say goodbye to the organisers, especially Adrian, Matilda and Enkel who have made everything happen, and in a wonderful spirit; and our guide Sebastian, who has set an impossibly high bar for any others to aspire to. We wish him well in his own exams, which start on Thursday! Albania has left a strong positive impression, and it will sit high on my list of places to explore more in the future, hopefully before too many others discover it. The airport affords the chance to spend the final Leke on brandy and figurines of Mother Teresa, and the flight the chance to finish problem N5, and discuss our geometry training regime with Rosie and Jacob as they work through some areal exercises.

2am is not a thrilling time to be arriving in Oxford, and 2.30am is not a thrilling time to be picking up solutions to past papers (and an even less thrilling time to discover that no such solutions have been handed in). But this has been a really enjoyable competition, at which the UK team were delightful company, and performed both strongly and stylishly at the competition, so it is all more than justified. We meet again at half-term in three weeks’ time to select the UK team for the IMO in Hong Kong, and hopefully explore some more interesting mathematics!

Balkan MO 2016 – UK Team Blog Part One

Posted on May 10, 2016 by dominicyeo

The Balkan Mathematical Olympiad is a competition for high school students from eleven countries in Eastern Europe, hosting on an annually rotating basis. For the 33rd edition it was Albania’s turn to host, and the UK was invited to participate as a guest nation.

A report with more mathematics, less frivolity and minimal chronological monotonicity can be found [SHORTLY].

Wednesday 4th May

I put the finishing touches to another draft of another chapter of my thesis, cajole the Statistics Department printer into issueing eighteen tickets, six consent forms and a terrifyingly comprehensive insurance policy, and head for Gatwick to meet the team. The UK imposes a policy that we will only take anyone to the Balkan MO once, so as to maximise the number of students who get to experience an international competition. The faces aren’t entirely new though – all six attended our winter programme in Hungary over New Year and the recent selection camp in Cambridge. They are showing the right level of excitement: the level that suggests they will enjoy the competition but won’t lose their passports in the next thirty minutes. As a point of trivia, this UK team are all sixth-formers, which, after checking not very carefully, doesn’t seem to have happened for any UK team for a long time, possibly not since 2008 when I was a contestant.

As of February this year, it’s now possible to fly direct to Albania on British Airways, which is a major improvement on the alternatives featuring either a seven-hour layover in Rome, or a nailbiting twenty-five minute interchange in Vienna. A drawback of the diary format is the challenging requirement to say interesting things about flights. In this instance, my principal challenge is to find some leftover room in my seat, as my neighbour’s physique has the same level of respect for the constraining power of armrests as the sea for the battlements of a child’s sandcastle. Across the aisle, Renzhi and Thomas face the twin challenges of a sheet of functional equations I’ve collated, and the well-meaning attempts of cabin attendants and their own neighbours to discuss said functional equations.

Later, over dinner next to Mother Teresa Airport in Tirana, we discuss the role of mathematics in recent films. Based on a sample size of at most two, we decide that `The Man who Knew Infinity’ is slightly better than `The Imitation Game’, partly because the former had fewer mathematical errors, or at least mispronunciations, about which Gerry feels strongly.

Thursday 5th May

The drawback of the new BA route is that it doesn’t run on Thursdays, so we are actually almost a full day early. Morning brings a cloudless summer’s day, and views of the imposing mountains that encircle Tirana. The students have assembled a healthy collection of past problems that they are keen to attempt as practice, and it seems natural to attempt this in a slightly more interesting place than the hotel lobby for at least some of the day.

Our guide Sebastian waves his Blackberry and rapidly conjures up an excursion to Mount Dajti, a small resort two-thirds of the way up a small mountain accessed from suburban Tirana via cable car. We follow a sign that seems to point to the summit, but the trail has distinctly horizontal ambitions. We are rewarded nonetheless with some pleasant views over the mountain range down past enclosed cerulean lakes down to the Adriatic, and even beyond to Italy.

Gerry is concerned about whether our return route is actually taking us where we want to go. He is right to be concerned, but not for that reason. It is the correct direction, but through a military base. Despite this, we make it back to the top of the cable car in the correct number of pieces. There’s the chance to alter this with some diverting activities, namely horse-riding and target-shooting. The targets are balloons, mounted on a clothes line at roughly horse-head-height. We move along.

Several years of attending maths competitions has increased both my ability to solve problems in Euclidean geometry, and also my suspicion of anything with a title like ‘Museum of National History’. I’m going to have to adjust the latter, because the recently-opened Albanian version, called BunkART, was actually excellent. It was housed in the five-level 108-room bunker built into the mountain to protect Enver Hoxha from nuclear attack. The rooms detailed the recent, fragmented history of the country, and were interspersed with aggressively modern art installations. In one basement which used to house the isotope filters, we were treated to a video loop of blood dripping onto barbed wire set to Mahler’s 5th Symphony.

While some regional competitions have adopted the ‘benign dictatorship’ approach to choosing the problems, the Balkan MO still has a problem selection phase. So I separate from the students and spend a pleasant few hours playing around with some of the proposals in the rooftop lounge of the leaders’ hotel on a balmy night in central Tirana.

Friday 6th May

The task for today is to construct a paper. A committee has selected a shortlist of problems, and we have to narrow this down to four, with one from each topic area, with an appropriate range of difficulty. The shortlist definitely contains some gems and some anti-gems, and more thoughts about these can be found in the official report.

The only dramatic moment comes when the Greek leader flourishes a webpage and an old IMO shortlist problem, which does indeed contain a proposed question as a lemma, and so it is rejected. Partly as a result of this, a medium geometry problem is chosen quickly; and the hard combinatorics shortly after lunch, since everyone likes it, and no-one can propose a better alternative. Selecting the final two problems, from number theory and algebra produces several combinatorial challenges in its own right. A rather complicated, multi-round election takes place (in which the UK, as a guest nation, does not get a say), and the final two problems are chosen, and the paper is complete.

Interestingly, this matches exactly the ideal paper I’d been hoping for last night, but with the middle questions the other way round. I think the UK students will enjoy it, and I’ll be very pleased for anyone from any country who solves the final problem. It’s fascinating to talk to the leaders of Bosnia and Montenegro, who discuss in detail why their respective education systems mean they are confident their students will struggle much more with Q3.

In the middle of the selection process, there was a rapid transfer to the students’ site in Vore, 15km away, to attend a brief opening ceremony. There is a warm speech from the deputy minister for education, some brief dancing, and the parade of teams. The wholesaler had a bargain on quartered polo shirts, so, unlike the UK flag they are carrying, our team are invariant under both reflection and rotation.

I am summoned to be an expert on the usage of English to prepare the final version of the paper. I feel that the problem authors have done an excellent job, and there is little work to do except suggest some extra sentence breaks and delete some appearances of the word ‘the’. Pity then the other leaders who return to the Harry Fultz school to translate and approve all the versions in their respective languages. It’s midnight as a I write this, and no sign of their return…

Saturday 7th May

This is what we’ve all come for, as the contestants are transported into Tirana for the 4.5 hours of the competition paper. They are allowed to ask questions of clarification during the first half hour. Twenty-five minutes pass, and we are untroubled, so we smugly conclude we must have achieved a wording with total clarity. In fact, the exam is starting slightly late, and a mild deluge begins, mostly concerning the definition of ‘injective’. Both the era of UK students asking joke questions and UK students asking genuine questions have passed, so I am left in peace.

Somehow, Enkel Hysnelaj has single-handedly produced LaTeX markschemes for all four problems overnight, and these are discussed at some length, though it’s to his credit that they didn’t require even longer. The leaders and deputies are then wheeled off on an excursion. Our destination is Kruje, famous as the hometown of Skenderbeg, the Albanian national hero, and just before that is Fushe-Kruje, famous as the place where George W. Bush’s watch was stolen during an official visit. On the way up to the castle and museum we pass through a bazaar where there is the opportunity to buy a carpet, a felt hat, or a mug decorated with a picture of Enver Hoxha. I will be sure to drop some hints to the UK students about ideal choices of gift for Gerry.

The scripts will be arriving a bit later, so there’s the chance for a wander around Tirana in the early evening sun. My planned trip to the Museum of Secret Surveillance is sadly foiled since it hasn’t yet been opened, but there are several more statues of Skenderbeg to enjoy. The question of why he wears a goat head on his helmet remains open. Since dinner is a mere two hours after another meat-centric five course lunch, I turn my attention to the UK scripts which have just arrived. I glance at questions 1 and 4 and the latter is mostly bare while the former is pointedly well-written. The same applies to question 3. All of our nagging about clear written work has very much been rewarded here. As a personal bonus, I can therefore spare time for a late dinner. My attempt at ordering a quick snack results in about a kilo of ribs with the ubiquitous lemons, but will hopefully deflate slightly during coordination in the morning.

Turan’s Theorem

Posted on May 1, 2016 by dominicyeo

Turan’s theorem gives bounds on the number of edges required in a graph on a fixed number of vertices n to guarantee it contains a complete graph of size r+1. Equivalently, an upper bound on the number of edges in a $K_{r+1}$ -free graph. For some of the applications and proofs, it may be more natural to look instead at the complement graph, for which the theorem becomes a statement about the existence or otherwise of an independent set of size r+1.

Rather than give an expression for the bound immediately, it is more natural to consider the Turan graph T(n,r), the maximal graph on n vertices without a copy of $K_{r+1}$ . This is constructed by dividing the vertices into r classes with ‘as equal size as possible’. That is, some classes have size $\lfloor \frac{n}{r}\rfloor$ and others have size $\lfloor \frac{n}{r}\rfloor +1$ . Then connect any pair of vertices which are not in the same class by an edge. This gives a complete r-partite graph on these classes. Since any collection of r+1 vertices contains at least two in the same class, it can’t contain a $K_{r+1}$ . Note that the complement of the complete r-partite graph is the union of r disjoint complete graphs on the classes.

There are a number of ways to enumerate the edges in T(n,r), and some can get quite complicated quite quickly. After a moderate amount of thought, this is my favourite. Let $n=\ell r+k$ , so T(n,r) has k classes of size (l+1) and (r-k) classes of size l. Pick an ordered pair of vertices uniformly at random. (So picking the same vertices is indeed an option, and is counted twice.) Then the probability they are the same class is

$\frac{k}{r}\cdot\frac{\ell+1}{n}+\frac{r-k}{r}\cdot \frac{\ell}{n} = \frac{1}{r}.$

So the probability they are in different classes is $\frac{r-1}{r}$ , and we can treat all of the $2n^2$ ordered pairs in this way, noting a) that we count everything twice; and b) we know a priori that we don’t have loops, so the fact that we’ve included these in the count doesn’t matter. We end up with the enumeration $(1-\frac{1}{r})\frac{n^2}{2}$ for the edges in T(n,r).

A standard proof

For both proofs, I find it slightly easier to work in the complement graph, where we are aiming for the largest number of edges with an independent set of size (r+1). Suppose we have a graph with the minimal number of vertices such that there’s no independent set of given size. Suppose also that there is an edge joining vertices v and w, such that $d(v)> d(w)$ . Then if we change v’s neighbourhood $\Gamma(v)$ so that it becomes the same as $\Gamma(w)$ , (that is, we replace v with a copy of w, and maintain the original edge vw), then it is easily checked that we still do not have an independent set of that size, but fewer edges.

Note that by attempting to make the neighbourhoods of connected vertices equal, we are making the graph look more like a union of complete components. We can do a similar trick if we have three vertices u,v,w such that there are edges between u and v and v and w, but not u and w. Then we know the degrees of u,v,w are the same by the previous argument, and so it can again be checked that making $\Gamma(u),\Gamma(w)$ the same as $\Gamma(v)$ , and adding the edge uw reduces the number of edges, and maintains the non-existence of the independent set.

The consequence of this is that we’ve shown that the minimum can only be attained when presence of edges is an equivalence relation (ignoring reflexivity). Thus the minimum is only attained for a union of at most r complete graphs. Jensen (or any root-mean-square type inequality) will then confirm that the true minimum is attained when the sizes of the r components are as equal as possible.

A probabilistic proof

The following probabilistic proof is courtesy of Alon and Spencer. The motivation is that in the (equality) case of a union of complete graphs, however we try to build up a maximal independent set, we always succeed. That is, it doesn’t matter how we choose which vertex (unconnected to those we already have) to add next – we will always get a set of size r. This motivates a probabilistic proof, as an argument in expectation will have equality in the equality case, which is always good.

Anyway, we build up an independent set in a graph by choosing uniformly at random a vertex which is not connected to any we have so far, until this set of vertices is empty. It makes sense to settle the randomness at the start, so give the vertices a uniform random labelling on [n], and at each stage, choose the independent vertex with minimal label.

Thus, a vertex v will be chosen for the independent set if, and only if, it has a smaller label than all of its neighbours, that is, with probability $\frac{1}{1+d(v)}$ . So the expected size of the independent set constructed in this fashion is

$\sum_{v\in V(G)} \frac{1}{1+d(v)}\ge \frac{V}{1+\bar d} = \frac{V}{1+\frac{2E}{V}}.$

One can chase through the expressions to get the bound we want back.

Olympiad example

The reason I was thinking about Turan’s theorem was a problem which the UK IMO squad was discussing. It comes from an American selection test (slightly rephrased): given 100 points in the plane, what is the largest number of pairs of points with $\ell_1$ distance in (1,2]?

The key step is to think about how large a collection of points can have this property pairwise. It is easy to come up with an example of four points which work, and seemingly impossible to come up with an example with five points. To prove this, I found it easiest to place a point at the origin, then explicitly work with coordinates relative the basis $(1,1),(1,-1)$ for fairly obvious reasons in this metric.

Anyway, once you are convinced that you can’t have five points with this property pairwise, you are ready to convert into a graph-theoretic statement. Vertices correspond to points, and edges link pairs of points whose distance is in (1,2] as required. We know from the previous paragraph that there is no copy of $K_5$ here, so Turan’s theorem bounds the number of edges, ie the number of suitable pairs.

It also tells us under what sort of circumstances the bound is attained, and from this, it’s natural to split the 100 points into four groups of 25, for example by taking four points which satisfy the condition pairwise (eg a diamond around the origin), and placing each group very near one of the points.

Extensions and other directions

The existence of a complete subgraph is reminiscent of Ramsey theory, which in one case is a symmetric version of Turan’s theorem. In Turan, we are adding enough edges to force a complete subgraph, while in the original form of Ramsey theory, we are asking how large the graph needs to be to ensure that for any edge configuration, either the original graph or the complement graph includes a complete subgraph. It makes a lot more sense to phrase this in terms of colours for the purpose of generalisation.

A natural extension is to ask about finding copies of fixed graphs H other than the complete graph. This is the content of the Erdos-Stone theorem. I’d prefer to say almost nothing rather than be vague, but the key difference is that the bound is asymptotic in the number of vertices rather than exact. Furthermore, the asymptotic proportion of vertices depends on the chromatic number of H, which tells you how many classes r are required to embed H in a (large if necessary) r-partite graph. So it is perhaps unsurprising that the limiting proportions end up matching the proportion of edges in the Turan graphs, namely r-1/r as r varies, which leaves the exact scaling open to further investigation in the case where H is bipartite (hence has chromatic number 2).

EGMO 2016 Paper II

Posted on April 14, 2016 by dominicyeo

Continuing from yesterday’s account of Paper I, this is a discussion of my thoughts about Paper II of EGMO 2016, happening at the moment in Busteni, Romania. This is not an attempt to describe official solutions, but rather to describe the thought process (well, a thought process) of someone tackling each question. I hope it might be interesting or useful, but for students, it will probably be more useful after at least some engagement with the problems. These are excellent problems, and reading any summary of solutions means you miss the chance to hunt for them yourself.

In actual news, you can follow the scoreboard as it is updated from Romania here. Well done to the UK team on an excellent performance, and hope everyone has enjoyed all aspects of the competition!

Question 4

Circles $\omega_1,\omega_2$ with the same radius meet at two points $X_1,X_2$ . Circle $\omega$ is externally tangent to $\omega_1$ at $T_1$ , and internally tangent to $\omega_2$ at $T_2$ . Prove that lines $X_1T_1,X_2T_2$ meet on $\omega$ .

Thought 1: I’m not the biggest fan of geometry ever, but I thought this looked like a nice problem, because it’s only really about circles, so I figured it probably wouldn’t require anything too exotic.

Thought 2: I bet lots of people try inversion. But the equal radius condition means I’m probably happy with the circles as they are. I hope lots of people don’t try to place the diagram in some co-ordinate system, even if it possible to do it sensibly (eg by making $\omega$ the reference circle).

Thought 3: The labelling of $X_1,X_2$ is unrelated to the rest of the indexing. So the intersection of $X_1T_2,X_2T_1$ should also lie on $\omega$ , and possibly has some relationship (antipodal?) to the point I actually need to find out. But I can’t think of any reason why it’s easier to prove two points lie on a circle than just one, so let’s leave this as a thought rather than an idea.

Idea 1: I drew a terrible diagram on the back of a draft of my abstract, and for once, this was actually kind of helpful. Forget about radii being equal, one of them wasn’t even a circle. Anyway, while drawing in the later points, I was struggling to make it look convincingly like all the lengths which were supposed to be equal were in fact equal. So the idea was: almost all the segments in the diagram (once I’ve defined the circle centres $O_{\omega_1}$ etc) have one of two lengths (the radii of $\omega_1,\omega$ – red and green-ish in the diagram below), and with this in mind I can forget about the circles. We’ve got a rhombus, which is even better than a parallelogram, which is itself a really useful thing to have in a configuration. Another consequence of the proliferation of equal lengths is that almost all triangles are isosceles, and we know that similarity of isosceles triangles is particularly easy, because you only have to match up one angle.

Idea 2: How to prove it? We have to prove that two lines and a circle concur. This is where I actually need to stop and think for a moment: I could define the point where the lines meet and try to show it’s on the circle, or intersect one line with the circle, and show it’s on the other line. Idea 1 basically says I’m doing the problem using lengths, so I should choose the way that fits best with lengths.

If I define the point P where $X_2T_2$ meets the circle (this was easier to draw in my diagram), then I know $PO_\omega=T_2 O_\omega$ and so on. Then there were loads of isosceles triangles, and some of them were similar, which led to more parallel lines, and from this you could reverse the construction in the other direction to show that P also lay on the other line.

Question 5

Let k, n be integers such that $k\ge 2,\, k\le n\le 2k-1$ . Place rectangular k x 1 or 1 x k tiles on an n x n chessboard in the natural way with no overlap until no further tile can be placed. Determine the minimum number of tiles that such an arrangement may contain.

Idea 1: It took me a while to parse the question. Minimum over what? I rephrased it in my head as: “to show the answer is eg n+5, I need to show that whenever you place n+4 tiles legally, you can’t add another. I also need to show that you can place n+5 such that you can’t add another.” This made life a lot easier.

Thought 1: What goes wrong if you take n=2k and beyond? Well, you can have two horizontal tiles on a given row. I’m not really sure how this affects the answer, but the fact that there is still space constraint for n<2k is something I should definitely use.

Diversion: I spent a while thinking that the answer was 4 and it was a very easy question. I spent a bit more time thinking that the answer was n, and it was a quite easy question, then realised that neither my construction nor my argument worked.

Thought 2: can I do the cases n=k,or 2k-1 or k+1? The answers were yes, unsure, and yes. The answer to k+1, which I now felt confident was actually four, was helpful, as it gave me a construction for k+2, …, 2k-1 that seemed good, even though it was clearly not optimal for 2k-1. Therefore, currently my potential answer has three regimes, which seemed unlikely, but this seemed a good moment to start trying to prove it was optimal. From now on, I’m assuming I have a configuration from which you can’t add another block.

Idea 2: About this diagram, note that once I’ve filled out the top-left (k+1)x(k+1) sub-board in this way, there are still lots of ways to complete it, but I do have to have (n-k-1) horizontal and (n-k-1) vertical tiles roughly where I’ve put them. Why? Because I can’t ‘squeeze in’ a vertical tile underneath the blue bit, and I can’t squeeze in a horizontal tile to the right of the blue bit. Indeed, whenever I have a vertical block, there must be vertical blocks either to the left or to the right (*) (or possibly both if we’re near the middle). We need to make this precise, but before doing that, I looked back at where the vertical blocks were in the proposed optimum, and it turns out that all but (k-1) columns include a vertical block, and these (k-1) columns are next to each other.

This feels like a great idea for two reasons: 1) we’ve used the fact that n<2k at (*). 2) this feels very pigeonhole principle-ish. If we had fewer tiles, we’d probably have either at least k columns or least k rows without a vertical (or, respectively, horizontal) tile. Say k columns don’t include a vertical tile – so long as they are next to each other (which I think I know) we can probably include a horizontal tile somewhere in there.

So what’s left to do? Check the previous sentence actually works (maybe it’s full of horizontal tiles already?), and check the numerics of the pigeonhole bound. Also work out how the case n=2k-1 fits, but it seems like I’ve had some (/most) of the good ideas, so I stopped here.

Question 6

I don’t actually want to say very much about this, because I didn’t finish off all the details. I want to talk briefly in quite vague terms about what to do if you think this problem looks scary. I thought it looked a bit scary because it looked similar to two number theoretic things I remember: 1) primes in arithmetic progressions. This is very technical in general, but I can remember how to do 3 mod 4 fairly easily, and 1 mod 4 with one extra idea; 2) if a square-free number can be written as a sum of two squares, this controls its factors modulo 4.

Vague Ideas: It seemed unlikely that this would involve copying a technical argument, so I thought about why I shouldn’t be scared. I think I shouldn’t be scared of the non-existence part. Often when I want to show there are no integer solutions to an equation, I consider showing there are no solutions modulo some base, and maybe this will be exactly what I do here. I’ll need to convert this statement about divisibility into an equation (hopefully) and check that $n\equiv 3,4$ modulo 7 doesn’t work.

For the existence of infinitely many solutions, maybe I’d use Chinese Remainder Theorem [1], or I’ll reduce it to something that I know has lots of solutions (eg Pythagoras), or maybe I can describe some explicit solutions?

Actual Idea 1: We’ve got $n^2+m | n^4$ , but this is a very inefficient statement, since the RHS is a lot larger than the LHS, so to be useful I should subtract off a large multiple of the LHS. Difference of two squares is a good thing to try always, or I could do it manually. Either way, I get $n^2+m | m^2$ which is genuinely useful, given I know m=1,2, …, 2n, because the RHS is now comparable in size to the LHS, so I’ve narrowed it down from roughly n^2 possibilities to just three:

$n^2+m=m^2,\quad 2(n^2+m)=m^2,\quad 3(n^2+m)=m^2.$ (*)

I’m going to stop now, because we’ve turned it into a completely different problem, which might be hard, but at least in principle this is solvable. I hope we aren’t actually scared of (*), since it looks like some problems we have solved before. I could handle one of these in a couple of lines, then struggled a bit more with the other pair. I dealt with one by recourse to some theory, and the final one by recourse to some theory after a lot of rearranging which I almost certainly got wrong, but I think I made an even number of mistakes rather than an odd number because I got the correct solution set modulo 7. Anyway, getting to (*) felt like the majority of the ideas, and certainly removed the fear factor of the Q6 label, so to fit the purpose of this discussion I’ll stop here.

[1] During one lunch in Lancaster, we were discussing why Chinese Remainder Theorem is called this. The claim was that an ancient Chinese general wanted to know the size of their army but it was too big to count, so had them arrange themselves into columns of various sizes, and counted the remainders. The general’s views on the efficiency of this algorithm remain lost in the mists of time.

EGMO 2016 Paper I

Posted on April 13, 2016 by dominicyeo

We’ve just our annual selection and training camp for the UK IMO team in Cambridge, and I hope it was enjoyed by all. I allotted myself the ‘graveyard slot’ at 5pm on the final afternoon (incidentally, right in the middle of this, but what England fan could have seen that coming in advance?) and talked about random walks on graphs and the (discrete) heat equation. More on that soon perhaps.

The UK has a team competing in the 5th European Girls Mathematical Olympiad (hereafter EGMO 2016) right now in Busteni, Romania. The first paper was sat yesterday, and the second paper is being sat as I write this. Although we’ve already sent a team to the Romania this year (where they did rather well indeed! I blame the fact that I wasn’t there.), this feels like the start of the olympiad ‘season’. It also coincides well with Oxford holidays, when, though thesis deadlines loom, I have a bit more free time for thinking about these problems. Anyway, last year I wrote a summary of my thoughts and motivations when trying the EGMO problems, and this seemed to go down well, so I’m doing the same this year. My aim is not to offer official solutions, or even outlines of good solutions, but rather to talk about ideas, and how and why I decided whether they did or didn’t work. I hope some of it is interesting.

You can find the paper in many languages on the EGMO 2016 website. I have several things to say about the geometry Q2, but I have neither enough time nor geometric diagram software this morning, so will only talk about questions 1 and 3. If you are reading this with the intention of trying the problems yourself at some point, you probably shouldn’t keep reading, in the nicest possible way.

Question 1

[Slightly paraphrased] Let n be an odd positive integer and $x_1,\ldots,x_n\ge 0$ . Show that

$\min_{i\in[n]} \left( x_i^2+x_{i+1}^2\right) \le \max_{j\in[n]} 2x_jx_{j+1},$

where we define $x_{n+1}=x_1$ cyclically in the natural way.

Thought 1: this is a very nice statement. Obviously when i and j are equal, the inequality holds the other way round, and so it’s interesting and surprising that constructing a set of pairs of inequalities in the way suggested gives a situation where the ‘maximum minimum’ is at least the ‘minimum maximum’.

Thought 2: what happens if n is actually even? Well, you can kill the right-hand-side by taking at least every other term to be zero. And if n is even, you really can take every other term to be even, while leaving the remaining terms positive. So then the RHS is zero and the LHS is positive.

The extension to this thought is that the statement is in danger of not holding if there’s a lot of alternating behaviour. Maybe we’ll use that later.

Idea 1: We can write

$2(x_i^2+x_{i+1}^2)=(x_i+x_{i+1})^2 + |x_i-x_{i+1}|^2, \quad 4x_ix_{i+1}=(x_i+x_{i+1})^2 - |x_i-x_{i+1}|^2,$

which gives insight into ‘the problem multiplied by 2’. This was an ‘olympiad experience’ idea. These transformations between various expressions involving sums of squares turn out to be useful all the time. Cf BMO2 2016 question 4, and probably about a million other examples. As soon as you see these expressions, your antennae start twitching. Like when you notice a non-trivial parallelogram in a geometry problem, but I digress. I’m not sure why I stuck in the absolute value signs.

This was definitely a good idea, but I couldn’t find a way to make useful deductions from it especially easily. I tried converting the RHS expression for i (where LHS attains minimum) into the RHS expression for any j by adding on terms, but I couldn’t think of a good way to get any control over these terms, so I moved on.

Idea 2: An equality case is when they are all equal. I didn’t investigate very carefully at this point whether this might be the only equality case. I started thinking about what happens if you start with an ‘equal-ish’ sequence where the inequality holds, then fiddle with one of the values. If you adjust exactly one value, then both sides might stay constant. It seemed quite unlikely that both would vary, but I didn’t really follow this up. In any case, I didn’t feel like I had very good control over the behaviour of the two sides if I started from equality and built up to the general case by adjusting individual values. Or at least, I didn’t have a good idea for a natural ordering to do this adjustment so that I would have good control.

Idea 3: Now I thought about focusing on where the LHS attains this minimum. Somewhere, there are values (x,y) next to each other such that $x^2+y^2$ is minimal. Let’s say $x\le y$ . Therefore we know that the element before x is at least y, and vice versa, ie we have

$\ldots, \ge y, x, y, \ge x,\ldots.$

and this wasn’t helpful, because I couldn’t take this deduction one step further on the right. However, once you have declared the minimum of the LHS, you are free to make all the other values of $x_i$ smaller, so long as they don’t break this minimum. Why? Because the LHS stays the same, and the RHS gets smaller. So if you can prove the statement after doing this, then the statement was also true before doing this. So after thinking briefly, this means that you can say that for every i, either $x_{i-1}^2+x_i^3$ or $x_i^2+x_{i+1}^2$ attains this minimum.

Suddenly this feels great, because once we know at least one of the pairs corresponding to i attains the minimum, this is related to parity of n, which is in the statement. At this point, I was pretty confident I was done. Because you can’t partition odd [n] into pairs, there must be some i which achieves a minimum on both sides. So focus on that.

Let’s say the values are (x,y,x) with $x\le y$ . Now when we try to extend in both directions, we actually can do this, because the values alternate with bounds in the right way. This key is to use the fact that the minimum $x^2+y^2$ must be attained at least every other pair. (*) So we get

$\ldots, \le x,\ge y,x,y,x,\ge y,\le x,\ldots.$

But it’s cyclic, so the ‘ends’ of this sequence join up. If $n\equiv 1$ modulo 4, we get $\ge y,\ge y$ next to each other, which means the RHS of the statement is indeed at least the LHS. If $n\equiv 3$ modulo 4, then we get $\le x,\le x$ next to each other, which contradicts minimality of $x^2+y^2$ unless x=y. Then we chase equality cases through the argument (*) and find that they must all be equal. So (after checking that the case $x\ge y$ really is the same), we are done.

Thought 3: This really is the alternating thought 2 in action. I should have probably stayed with the idea a bit longer, but this plan of reducing values so that equality was achieved often came naturally out of the other ideas.

Thought 4: If I had to do this as an official solution, I imagine one can convert this into a proof by contradiction and it might be slightly easier, or at least easier to follow. If you go for contradiction, you are forcing local alternating behaviour, and should be able to derive a contradiction when your terms match up without having to start by adjusting them to achieve equality everywhere.

Question 3

Let m be a positive integer. Consider a 4m x 4m grid, where two cells are related to each other if they are different but share a row or a column. Some cells are coloured blue, such that every cell is related to at least two blue cells. Determine the minimum number of blue cells.

Thought 1: I spent the majority of my time on this problem working with the idea that the answer was 8m. Achieved by taking two in each row or column in pretty much any fashion, eg both diagonals. This made me uneasy because the construction didn’t take advantage of the fact that the grid size was divisible by 4. I also couldn’t prove it.

Thought 2: bipartite graphs are sometimes useful to describe grid problems. Edges correspond to cells and each vertex set to row labels or column labels.

Idea 1: As part of an attempt to find a proof, I was thinking about convexity, and why having exactly two in every row was best, so I wrote down the following:

Claim A: No point having three in a row.

Claim B: Suppose a row has only one in it + previous claim => contradiction.

In Cambridge, as usual I organised a fairly comprehensive discussion of how to write up solutions to olympiad problems. The leading-order piece of advice is to separate your argument into small pieces, which you might choose to describe as lemmas or claims, or just separate implicitly by spacing. This is useful if you have to do an uninteresting calculation in the middle of a proof and don’t want anyone to get distracted, but mostly it’s useful for the reader because it gives an outline of your argument.

My attempt at this problem illustrates an example of the benefit of doing this even in rough. If your claim is a precise statement, then that’s a prompt to go back and separately decide whether it is actually true or not. I couldn’t prove it, so started thinking about whether it was true.

Idea 2: Claim A is probably false. This was based on my previous intuition, and the fact that I couldn’t prove it or get any handle on why it might be true. I’d already tried the case m=1, but I decided I must have done it wrong so tried it again. I had got it wrong, because 6 is possible, and it wasn’t hard from here (now being quite familiar with the problem) to turn this into a construction for 6m in the general case.

Idea 3: This will be proved by some sort of double-counting argument. Sometimes these arguments turn on a convexity approach, but when the idea is that a few rows have three blue cells, and the rest have one, this now seemed unlikely.

Subthought: Does it make sense for a row to have more than three blue cells? No. Why not? Note that as soon as we have three in a row, all the cells in that row are fine, irrespective of the rest of the grid. If we do the problem the other way round, and have some blues, and want to fill out legally the largest possible board, why would we put six in one row, when we could add an extra row, have three in each (maintaining column structure) and be better off than we were before. A meta-subthought is that this will be impossible to turn into an argument, but we should try to use it to inform our setup.

Ages and ages ago, I’d noticed that you could permute the rows and columns without really affecting anything, so now seemed a good time to put all the rows with exactly one blue cell at the top (having previously established that rows with no blue cell were a disaster for achieving 6m), and all the columns with one blue cell at the left. I said there were $r_1,c_1$ such rows and columns. Then, I put all the columns which had a blue cell in common with the $r_1$ rows next to the $c_1$ columns I already had. Any such column has at least three blues in it, so I said there were $c_3$ of these, and similarly $r_3$ rows. The remaining columns and rows might as well be $r_0,c_0$ and hopefully won’t matter too much.

From here, I felt I had all the ingredients, and in fact I did, though some of the book-keeping got a bit fiddly. Knowing what you are aiming for and what you have means there’s only one way to proceed: first expressions in terms of these which are upper bounds for the number of columns (or twice the number of columns = rows if you want to keep symmetry), and lower bounds in terms of these for the number of blue cells. I found a noticeable case-distinction depending on whether $r_1\le 3c_3$ and $c_1\le 3r_3$ . If both held or neither held, it was quite straightforward, and if exactly one held, it got messy, probably because I hadn’t set things up optimally. Overall, fiddling about with these expressions occupied slightly more time than actually working out the answer was 6m, so I don’t necessarily have a huge number of lessons to learn, except be more organised.

Afterthought 2: Thought 2 said to consider bipartite graphs. I thought about this later while cycling home, because one can’t (or at least, I can’t) manipulate linear inequalities in my head while negotiating Oxford traffic and potholes. I should have thought about it earlier. The equality case is key. If you add in the edges corresponding to blue cells, you get a series of copies of $K_{1,3}$ , that is, one vertex with three neighbours. Thus you have three edges for every four vertices, and everything’s a tree. This is a massively useful observation for coming up with a very short proof. You just need to show that there can’t be components of size smaller than 4. Also, I bet this is how the problem-setter came up with it…

Linear Algebra II: Eigenvectors and Diagonalisability

Posted on February 25, 2016 by dominicyeo

This post continues the discussion of the Oxford first-year course Linear Algebra II. We’ve moved on from determinants, and are now considering eigenvalues and eigenvectors of matrices and linear maps.

A good question to ask is: what’s the point of knowing about eigenvectors? I can think of a quick answer and a longer answer. The quick answer is that whenever we have a mapping of any kind, it is natural to ask about its fixed points. And since we are thinking about vector spaces and linear maps, if we can’t find any fixed points, we might nonetheless be able to find the best thing, some vectors whose direction is fixed by the map. In general, knowing about fixed points of a mapping might tell us other more qualitative properties, including the behaviour seen when you apply the map iteratively a large number of times. (Indeed a recent post discusses this exact problem for positive matrices in a context relevant to a chapter of my thesis…)

A more specific answer concerns bases. Recall that a linear map is defined independently of any basis: it’s just a map from the vector space to itself. We can express the linear map via a matrix with respect to some basis, but how to choose the basis? We could always choose the canonical basis in $\mathbb{R}^n$ , since it’s easy to do vector and matrix calculations when most of the entries of all the vectors are zero. We also have a good visual idea (at least in up to three dimensions) of what a matrix might mean with respect to that basis. If we needed to divide the three-dimensional world around us into small volumes, we’d tend to describe it with small cubes rather than small arbitrary parallelopipeds.

But once we know something about the linear map, we might want to choose a basis of vectors on which the behaviour of the map is particularly easy to describe. And eigenvectors fulfil precisely this role. If we are able to choose a basis of eigenvectors, describing the map’s action, either abstractly, or via a (diagonal) matrix, is very straightforward. If we are given a matrix to begin with, we know how to do a change of basis, and changing to the basis of eigenvectors is precisely what’s going when we write $A=P^{-1}DP$ , where D is a diagonal matrix. We construct P by taking its columns to be these eigenvectors. In particular, for a given vector x, y=Px is the vector giving the coefficients of x in the basis of eigenvectors.

So the case where we have a basis of eigenvectors is particularly useful, and in this case, we say the matrix or the map is diagonalisable. Remember how we find eigenvalues. If there exists a non-zero vector x satisfying $Ax=\lambda x$ , then x is in the kernel of $A-\lambda I$ . As we discussed last time, introducing the determinant gives a much more manageable way to verify which values of $\lambda$ result in $A-\lambda I$ having a non-trivial kernel. In particular, if non-zero x is in the kernel, we have $\mathrm{det}(A-\lambda I)=0$ , and this leads to a polynomial of degree n (the dimensional of the vector space / size of the matrix) for $\lambda$ , called the characteristic polynomial $\chi_A(z)$ , which has the eigenvalues as its roots.

If we agree to work over the complex field, then this is good, because it means we always have eigenvalues, and so it becomes sensible to talk about exactly how many eigenvalues and eigenvectors we have. Observe that if we restrict to real vector spaces, this might not be the case. In the plane, the rotation by $\pi/2$ for example has no fixed vectors.

Multiplicities of eigenvalues

We call the algebraic multiplicity $\alpha(\lambda)$ of an eigenvalue $\lambda$ to be the exponent of the factor $(z-\lambda)$ in the factorisation of the characteristic polynomial. To define the geometric multiplicity, observe that all the eigenvectors with eigenvalue $\lambda$ form a subspace, and so it is meaningful to talk about the dimension of this subspace (‘eigenspace’), which is the geometric multiplicity $\gamma(\lambda)$ . There are two facts that one needs to remember. The slightly less obvious one is that $\gamma(\lambda)\le \alpha(\lambda)$ for all $\lambda$ . One can see this by, for example, working in a basis that extends a basis of the $\lambda$ -eigenspace. Observe at this stage that the sum of the algebraic multiplicities has to be n by definition, while the sum of geometric multiplicities is at most n. And this makes sense, because the space spanned by all the eigenvectors is a subspace, and so has dimension at most n.

The more obvious, but more frequently forgotten result is that

$\alpha(\lambda)\ge 1 \quad \iff \quad \gamma(\lambda)\ge 1,$

which is simply a consequence of the property discussed a few paragraphs previously concerning the kernel of $A-\lambda I$ .

In particular, we might make the heuristic observation that ‘most’ polynomials of degree n have n distinct roots. This is certainly true for quadratics: there is only one value that the discriminant can take such that we see a repeated root. Alternatively, imagine shifting the quadratic up and down (in a complex way if necessary); again there is only one moment at which it might have a repeated root. This observation can be generalised easily to higher degree polynomials in a number of ways.

So if we lift this observation across to matrices, we see that most matrices have n distinct eigenvalues, and thus have n linearly independent eigenvectors which form a basis, hence the matrix is diagonalisable. I think it’s really worth reflecting on this, since much of a first exploration into linear algebra ends up treating exactly the case where the matrix is not diagonalisable.

The principal example of a non-diagonalisable matrix is $\begin{pmatrix}2&1\\0&2\end{pmatrix}$ , where the 2s can be replaced by any value, and the 1 can be replaced by an non-zero value. There’s plenty to learn about to what extent versions of this matrix of higher size represent all non-diagonalisable matrices, but such an exposition of Jordan normal form comes next year for the students taking this course.

It probably is worth saying now though, that this example gives a good sanity check for whether a method is actually using diagonalisability correctly. For example, it is easily seen that elementary row operations to not preserve diagonalisability by starting from $\begin{pmatrix}2&0\\0&2\end{pmatrix}$ and ending up at our counter-example. One could also argue from this that the set of non-diagonalisable matrices are dense within the set of matrices with a repeated eigenvalue. That is, having a repeated eigenvalue but full eigenspace is doubly-infinitely-unlikely.

Cayley-Hamilton theorem

Anyway, among other results, we also saw the Cayley-Hamilton theorem, which states that a matrix A satisfies its own characteristic equation. That is $\chi_A(A)=0$ , where the zero on the right-hand side is the zero matrix. It’s tempting to substitute A into the expression $\mathrm{det}(A-\lambda I)$ , but of course this is not valid. Indeed imagine a typical eigenvalue determinant matrix with terms like $(7-\lambda)$ on the diagonal; it doesn’t make sense to substitute a matrix for $\lambda$ as one of the entries of the overall matrix!

Fortunately, we can argue convincingly in the case where A is a diagonalisable matrix. Remember that $\chi_A(A)$ is a matrix. Now looki at the action of $\chi_A(A)$ on any eigenvector v, corresponding to eigenvalue $\lambda$ . Applying some power of A to v gives v multiplied by the same power of $\lambda$ , and so we end up with

$\chi_A(A)v = \chi_A(\lambda)v = 0.$

This only worked when v was an eigenvector, but fortunately there is a basis of eigenvectors if A is diagonalisable, and so $\chi_A(A)v=0$ for all v, hence $\chi_A(A)=0$ .

But $\chi_A(A)$ is just a matrix-valued function of A. If you think about it, $\chi_A$ is a monic polynomial, all of whose non-leading coefficients are multinomials of degree at most n-1 in the entries of A. Furthermore, these multinomials have (non-negative) integer coefficients. Therefore the entries of $\chi_A(A)$ are multinomials of degree at most 2n-1 in the entries of A, and again have (non-negative) integer coefficients.

Even without the integrality of the coefficients, this says that, under any reasonable definition of continuity of matrices (which could be induced from any topology on $\mathbb{R}^{n\times n}$ ) the function $\chi_A(A)$ should be continuous as a function of A. But we’ve shown $\chi_A(A)=0$ for all diagonalisable A, and also argued that most complex-valued matrices are diagonalisable. Turning this into a formal statement about denseness means that we’ve shown the Cayley-Hamilton theorem for non-diagonalisable matrices also. It feels that because the coefficients are non-negative integers, we might also have shown the result for other fields too, but I have minimal knowledge or recollection at the moment of the things one has to check for this sort of result.

It’s worth ending with the brief comment that Cayley-Hamilton is useful, among other reasons because it enables us to write the inverse of A as a polynomial of degree at most n-1 in terms of A. In many settings this is a lot easier to work with in terms of calculations than an argument with minors.

Linear Algebra II: Determinants 2

Posted on February 25, 2016 by dominicyeo

In the previous post, we introduced determinants of matrices (and by extension linear maps) via its multilinearity properties, and as the change-of-volume factor. We also discussed how to calculate them, via row operations, or Laplace expansion, or directly via a sum of products of entries over permutations.

The question of why this is ever a useful quantity to consider remains, and this post tries to answer it. We’ll start by seeing one example where this is a very natural quantity to consider, and then the main abstract setting, where the determinant is zero, and consider a particularly nice example of this.

Jacobeans as a determinant

We consider integration by substitution. Firstly, in one variable: when it comes to Riemann integration of a function g(x) with respect to x, we view dx as the width of a small column which approximates the function near x. Now, if we reparameterise, that is if we write x=f(y) for some well-behaved (in particular differentiable) function f, then the width of the column is dx= dy.(dx/dy)=f'(y) dy. This may be negative, if y is decreasing while x is increasing, but for now let’s not worry about this overly, for example by assuming the function g is non-negative. Thus if we want to integrate with y as the variable, we multiply the integrand by this factor $|f'(y)|$ .

What about in higher dimensions? We have exactly the same situation, only instead of two-dimensional columns, we have (n+1)-dimensional columns. We then multiply the n-dimensional volume of the base by the height, again given by $g(\mathbf{x})$ . If we have a similar transformation of the base variable $\mathbf{x}=f(\mathbf{y})$ , we differentiate to get

$\mathrm{d}x_i = \sum_{j=1}^n\frac{\mathrm{d}f_i}{\mathrm{d}y_j} \mathrm{d}y_j.$

In other words

$\mathrm{d}\mathbf{x}= J \mathrm{d}\mathbf{y},$

where J is the Jacobean matrix of partial deriatives. In particular, we know how to relate the volume $[0,\mathrm{d}x_1]\times\ldots\times [0,\mathrm{d}x_n]$ to the volume $[0,\mathrm{d}y_1]\times \ldots\times [0,\mathrm{d}y_n]$ . It’s simply the determinant of the Jacobean J. So if we want to integrate with respect to $\mathbf{y}$ , it only remains to pre-multiply the integrand by $|\mathrm{det}J|$ and proceed otherwise as in the one-dimensional case.

Det A = 0

A first linear algebra course might well motivate the introducing matrices as a notational shortcut for solving families of linear equations, $Ax=b$ . The main idea is that generally we can solve this equation uniquely. Almost all of the theory developed in such a first linear algebra course deals with the case when this fails to hold. In particular, there are many ways to characterise this case, and we list some of them now:

Ax=b has no solutions for some b;
A is not invertible;
A has non-trivial kernel, that is, with dimension at least one;
A does not have full rank, that is, the image has dimension less than n;
The columns (or indeed the rows) are linearly dependent;
The matrix can be row-reduced to a matrix with a row of zeroes.

It is useful that these are equivalent, as in abstract problems one can choose whichever interpretation from this list is most relevant. However, all of these are quite hard to check. Exhibiting a non-trivial kernel element is hard – one either has to do manual row-reduction, or the equivalent in the context of linear equations. But we can add the characterisation

det A = 0;

to the list. And this is genuinely much easier to check for specific examples, either abstract or numerical.

Let’s quickly convince ourselves of a couple of these equivalences. Determinant is invariant under row-reductions, and by multilinearity it is certainly the case that det A = 0 if A has a row of zeroes. We also said that A is the change-of-volume factor. Note that A is a map from the domain to its image, so if A has less than full rank, then any set in the image has zero volume.

The Vandermonde matrix

This is a good example of this theory in practice. Consider the Vandermonde matrix where each row is a geometric progression:

$V=\begin{pmatrix}1&\alpha_1&\ldots&\alpha_1^{n-1}\\1&\alpha_2&\ldots&\alpha_2^{n-1}\\ \vdots&\vdots&\ddots&\vdots\\ 1&\alpha_n&\ldots&\alpha_n^{n-1}\end{pmatrix}.$

Now suppose we attempt to solve

$V\begin{pmatrix}a_0\\a_1\\ \vdots\\ a_{n-1}\end{pmatrix}=\begin{pmatrix}b_1\\b_2\\ \vdots \\ b_n\end{pmatrix}.$

There’s a natural interpretation to this, that’s especially clear with this suggestive notation. Each row corresponds to a polynomial, where the coefficients are given by the $(a_0,a_1,\ldots,a_{n-1})$ , and the argument is given by $\alpha_i$ .

So if we try to solve for $(a_0,a_1,\ldots,a_{n-1})$ , given $(\alpha_1,\ldots,\alpha_n)$ and $(b_1,\ldots,b_n)$ , we are asking whether we can find a polynomial P with degree at most n-1 such that $P(\alpha_i)=b_i$ for $i=1,\ldots,n$ . Lagrange interpolation gives an argument where we just directly write down the relevant polynomial, but we can also deploy our linear algebraic arguments too.

The equivalence of all these statements means that to verify existence and uniqueness of such a polynomial, we only need to check that the Vandermonde matrix has non-zero determinant. And in fact there are a variety of methods to show that

$\mathrm{det}V=\prod_{1\le i< j}\le n(\alpha_j-\alpha_i).$

For the polynomial question to be meaningful, we would certainly demand that the $(\alpha_i)$ are distinct, and so this determinant is non-zero, and we’ve shown that n points determine a degree (n-1) polynomial uniquely.

If we multiply on the left instead, suppose that we are considering a discrete probability distribution X that takes n known values $(\alpha_1,\ldots,\alpha_n)$ with unknown probabilities $(p_1,\ldots,p_n)$ . Then we have

$(p_1,\ldots,p_n) V = (1,\mathbb{E}X, \mathbb{E}[X^2],\ldots, \mathbb{E}[X^{n-1}]).$

So, again by inverting the Vandermonde matrix (which is know is possible since its determinant is non-zero…) we can recover the distribution from the first (n-1) moments of the distribution.

A similar argument applies to show that the Discrete Fourier Transform is invertible, and in this case (where the $\alpha_i$ s are roots of unity), the expression for the Vandermonde determinant is particularly tractable.

Linear Algebra II: Determinants 1

Posted on February 25, 2016 by dominicyeo

This term, I’m giving tutorials on a course that’s new to me, the apparently notorious ‘Linear Algebra II’ for first year undergraduates. I can appreciate how it might have ended up with this reputation, but as always, every challenge is also an opportunity, So I’m going to (try to) write a short series of blog posts about what we’ve discussed in the tutorials.

The first problem sheet-and-a-half concerned determinants of matrices. There are three things worth addressing here:

What are abstract definitions, and which is most useful in each setting?
How to actually calculate them?
What’s the overall point?

The answers are obviously not completely unrelated, but we’ll probably defer the third question to a second post.

The determinant is a map from the set of matrices $\mathcal{M}_n$ to the base field (hereafter assumed to be $\mathbb{R},\mathbb{C}$ ). The Oxford course defines it through its properties:

Multilinear in the columns of the matrix.
Equal to zero if two columns are equal.
Equal to one if the matrix is the identity.

One then checks that there is a unique such map, and so from now on it’s reasonable to call it the determinant of the matrix. It will follow from pretty much any consequence that we can replace ‘columns’ with ‘rows’ throughout and get the same map.

Other definitions

We have a closed form expression for the determinant given via permutations of n

$\mathrm{det}(A)=\sum_{\sigma\in \Sigma_n} \mathrm{sign}(\sigma) a_{1\sigma(1)}\ldots a_{n\sigma(n)}.$

We’ll come back to a discussion of when this particular definition is useful. It can be derived by carefully transforming the identity matrix into A, using the operations which are mentioned in the original definition of the determinant, in particular, keeping track of the number of transpositions of columns.

It’s clear from any definition that the determinant is a polynomial of degree n in the entries of the matrix, but this definition will be useful if you want to make some more precise comment on the nature of this polynomial. For example, if entries of the matrix are polynomials in x of various degree (think of the eigenvalue equation for example) this allows you to control (or at least bound) the overall degree of the determinant as a polynomial in x.

The determinant is also the volume of the n-dimensional parallelopiped formed by the column vectors of the matrix. This is easy to check in two dimensions, for the matrix $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ :

To calculate the area of the central parallelogram, we have to subtract the area of two small rectangles and four small triangles from the outer rectangle, obtaining

$(a+b)(c+d)-2bc - \frac12(ac+ac+bd+bd)=ad-bc,$

as we expect. This calculation is harder to execute in higher dimensions, and certainly harder to visualise.

Maybe, though, we don’t have to, so long as we can reassure ourselves that this volume satisfies the implicit definition of the determinant map at the start. Multilinearity in the columns is not that hard to see. If we multiply the jth column by some constant, we are stretching the parallelopiped by the same constant factor in one direction, and so the volume grows appropriately. The additivity property can similarly be thought of as joining together two parallelopipeds at their common face (which is common since the other column vectors have to be constant in this construction). If two column vectors are equal, then clearly this volume actually has dimension at most n-1, and thus volume zero, so the final two conditions are genuinely easy to check.

The challenge here is that there is a direction involved. Determinants can be negative, but in our classical viewpoint, areas generally are not. In 2D, we can think of this as saying that the area is positive if the vector (b,d) lies anti-clockwise from (a,c) in the parallelogram, while is it negative otherwise. Again, this is harder to visualise in higher dimensions, but it is at least plausible that one could develop a similar decomposition. Ultimately, we are happy with the notion of directed lengths (ie vectors on the real line), and these are easy to add up without having to separate into cases, and the case holds for areas and higher-dimensional volumes.

Evaluating determinants

If we actually want to compute the determinant of a given matrix, the sum over permutations is intractable since it doesn’t have any natural splits into stages. The implicit definitions and this area consideration are clearly useless for all but the most special of examples.

The Laplace expansion is the usual algorithm to calculate the determinant of an n x n matrix. You pick a row (or a column), and evaluate the determinants of the (n-1) x (n-1) minor matrices given by deleting this row (or column), and each column (or row) in turn. This leaves us with n determinants of smaller matrices, which we pre-multiply by the entries in the original deleted row (or column), and add up in an alternating way (*). This is highly computationally intensive for large matrices, but for 3×3 and 4×4 can be done by hand with probability of an error bounded away from 1.

There is the flexibility to choose the reference row or column. Since the entries of these affect the sum through small products, it is highly convenient to choose a row or column with a lot of zeros. In particular, if there’s a row or column with exactly one non-zero entry, this is an ideal candidate.

The sum over permutations also works well when a lot of the entries are zero, because then a lot of the permutations give a summand which is zero. Upper-triangular matrices are a good example: only one permutation (the identity permutation) avoids all the zero elements underneath the diagonal.

One can also observe from the multilinearity property of the determinant map that there are lots of operations we can apply to the matrix which leave the determinant fixed. These are often called elementary row operations, though obviously we can apply them to the columns as well. To summarise, if we interchange two rows, the sign of the determinant is reversed. And if we add some multiple of one row to any other row, the determinant stays the same.

When matrices are not square, it’s quite important to be specific about exactly what form you can reduce a general matrix to via such row operations, but in this context, it’s not hugely important. Reduced echelon form (without the condition that leading coefficients will be one) is achievable, but this is a special case of an upper triangular matrix, for which the determinant is given by the product of the diagonal entries, ie is easy.

Whether this is substantially easier than Laplace expansion depends on the matrix itself and taste, both to do manually, and to code.

(*) I’m not a fan personally of this alternating definition. It seems to me much more natural to define the minor as

$M^{i,j}=(a_{i+k,j_\ell})_{1\le k,\ell\le n-1},$

with indices taken modulo n. Then you don’t have any $\pm 1$ s in the Laplace expansion.

Using determinants in abstract problems

So the determinant gives directly the area of the image (under A) of the unit hypercube. By linearity (of A), it is easy to see that it also gives the scale factor of the area change (under A) of any hyper-cuboid, parallel to the conventional axes, anywhere in the space. Then, eg by approximating any sensible n-dimensional shape (*) as a union of such hyper-cuboids, we can show that in fact the area of any sensible shape increases by a factor (det A) under application of A.

This is a good thing to remember, because it is an excellent heuristic for seeing why the determinant of a linear map is basis-independent. It also gives a much easier proof of the key result

$\mathrm{det}(AB)=\mathrm{det}(A) \mathrm{det}(B),$

than that given by fixing B and viewing det(AB) as a map from matrices to the field, just like the original definition of determinant.

Some of the theory in the course is proved using elementary row operations. But these invite complicated notation, so are best used only in simple arguments, or when things are fairly explicit to begin with. Given an abstract problem about determinants of matrices, it is often tempting to induct on the size of the matrix in some way. I think it’s worth saying that even though the Laplace expansion is explicitly set up in this way, the notation involved is also likely to be annoying here, while permutations are easy to describe inductively: eg let $\sigma(1)=k$ , then view the remainder of the permutation as a bijection $\{2,3,\ldots,n\}\rightarrow [n]\backslash \{k\}$ .

Shortly, we’ll have a second post answering the final question: what’s the point of working with determinants? We’ve already seen half an answer, in that they describe the change-of-volume factor of a matrix (or linear map), but this can be substantially developed.

Lagrange multipliers Part Two

Posted on January 31, 2016 by dominicyeo

My own question on last week’s BMO2 notwithstanding, inequalities seem out of fashion at the moment among mainstream international olympiads. Such problems often involve minimising some function subject to a constraint, and word has, over the years, filtered down to students interested in such things, that there’s a general method for achieving this via Lagrange multipliers. The motivation for my talk in Hungary, summarised by the previous post and this one, is to dispute the claim made by some of the UK students that these are hard to justify rigorously. I dispute this because I don’t think it’s qualitatively much harder to justify Lagrange multipliers rigorously than an unconstrained optimisation problem, whereas I would claim instead that Lagrange multipliers are merely unlikely to work at a computational level on the majority of olympiad problems.

Unconstrained optimisation in two variables

Before we can possibly discuss constrained optimisation, we should discuss unconstrained optimisation. That is, finding minima of a function of several variables. We don’t lose too much by assuming that our function f(x,y) depends on two variables.

Recall that our method in the previous post for justifying the A-level approach to minima was to find a necessary condition to be a local minimum, and also a general reason why there should be a global minimum. That way, if there are finitely many points satisfying the condition, we just check all of them, and the one with the smallest value of f is the global minimum. We’ll discuss the existence of the global minimum later.

If we hold one coordinate fixed, the local variation of a function is equivalent to the one-dimensional case.

$f(x+h,y)-f(x,y)= h\frac{\partial f}{\partial x}(x,y)+O(h^2).$

In general we want to vary both variables, which is fine since

$f(x+h,y+\ell)-f(x+h,y)=\ell \frac{\partial f}{\partial y}(x+h,y) + O(h^2).$

But since we really want everything to be determined by the function at (x,y), we really want

$\frac{\partial f}{\partial y}(x+h,y) \approx \frac{\partial f}{\partial y}(x,y),$

and so we be mindful that we may have to assume that both partial derivatives are continuous everywhere they exist. Once we have this though, we can rewrite as

$f(x+h,y+\ell) - f(x,y)= h\frac{\partial f}{\partial x}(x,y) + \ell \frac{\partial f}{\partial y}(x,y) + O(h^2)$

$= (\frac{\partial f}{\partial x}(x,y) ,\frac{\partial f}{\partial y}(x,y) )\cdot (h,\ell) + O(h\vee \ell^2).$

In particular, if we define grad of f to be $\nabla f(x,y)=(\frac{\partial f}{\partial x}(x,y), \frac{\partial f}{\partial y}(x,y) )$ and apply a similar argument to that which we used in the original setting. If $\nabla f(x,y)\ne 0$ , then we can choose some small $(h,\ell)$ , such that $f(x+h,y+\ell)<f(x,y)$ . Thus a necessary condition for (x,y) to be a local minimum for f is that $\nabla f=0$ .

Lagrange multipliers

This is natural time to discuss where Lagrange multipliers emerge. The setting now is that we still want to minimise some function $f(\mathbf{x})$ , but only across those values of $\mathbf{x}$ which satisfy the constraint $g(\mathbf{x})=0$ .

But our approach is exactly the same, namely we find a necessary condition to be a local minimum subject to the condition. As before, we have

$f(\mathbf{x}+\mathbf{h}) - f(\mathbf{x}) = \mathbf{h}\cdot \nabla f + O(|\mathbf{h}|^2),$

but we are only interested in those small vectors $\mathbf{h}$ for which $\mathbf{x}+\mathbf{h}$ actually satisfies the constraint, namely $g(\mathbf{x}+\mathbf{h})=0$ . But then

$0 = g(\mathbf{x}+\mathbf{h})- g(\mathbf{x})=\mathbf{h}\cdot \nabla g + O(|\mathbf{h}|^2).$

From this, we conclude that the set of small relevant $\mathbf{h}$ is described by $\mathbf{h}\nabla g=O(|\mathbf{h}|^2)$ . And now we really can revert to the original argument. If there’s a small $\mathbf{h}$ such that $\mathbf{h}\cdot \nabla g=0$ but $\mathbf{h}\cdot \nabla f \ne 0$ , then we can find some $\mathbf{h'_+},\mathbf{h'_-}=\pm \mathbf{h}+O(|\mathbf{h}|^2)$ such that at least one of $f(\mathbf{h'_+}),f(\mathbf{h'_-})<f(\mathbf{h})$ .

So a necessary condition to be a constrained local minimum is that every vector which is perpendicular to $\nabla g$ must also be perpendicular to $\nabla f$ . From which it follows that these two vectors must be parallel, that is $\nabla f(\mathbf{x})=\lambda \nabla g(\mathbf{x})$ , where $\lambda$ is the so-called Lagrange multiplier. Of course we must also have that $g(\mathbf{x})=0$ , and so we have a complete characterisation for a necessary condition that the constrained optimisation has a local minimum at $\mathbf{x}$ , assuming that all the derivatives of both f and g exist with suitable regularity near $\mathbf{x}$ .

Technicalities

The point of setting up the one-variable case in the unusual way in the previous post was to allow me to say at this stage: “it’s exactly the same”. Well, we’ve already seen an extra differentiability condition we might require, but apart from that, the same approach holds. Multi-variate continuous functions also attain their bounds when the domain is finite and includes its boundary.

Checking the boundary might be more complicated in this setting. If the underlying domain is $\{x,y,z\ge 0\}$ , then one will have to produce a separate argument for why the behaviour when at least one of the variables is zero fits what you are looking for. Especially in the constrained case, it’s possible that the surface corresponding to the constraint doesn’t actually have a boundary, for example if it is the surface of a sphere. Similarly, checking that the objective function gets large as the variables diverge to infinity can be annoying, as there are many ‘directions’ down which to diverge to infinity.

Motivating Cauchy-Schwarz

In practise, you probably want to have such methods in hand as a last resort on olympiad problems. It’s always possible that something will slip through the net, but typically problem-setters are going to trying to ensure that their problems are not amenable to mindless application of non-elementary methods. And even then, one runs the risk of accusations of non-rigour if you don’t state exact, precise results which justify everything which I’ve presented above.

One thing that can be useful, on the other hand, is to observe that the Lagrange multiplier condition looks a lot like the equality condition for Cauchy-Schwarz. So, even if you can’t solve the family of Lagrange multiplier ‘equations’, this does suggest that applying Cauchy-Schwarz to the vectors involved might give you some insight into the problem.

The following inequality from the IMO 2007 shortlist is a good example.

Suppose $a_1,\ldots,a_{100}\ge 0$ satisfy $a_1^2+\ldots+a_{100}^2=1$ . Prove that

$a_1^2a_2+a_2^2a_3+\ldots + a_{100}^2 a_1<\frac{12}{25}.$

We shouldn’t be perturbed by the strictness. Maybe we’ll end up showing a true bound in terms of surds that is less neat to write down…

Anyway, applying Lagrange multipliers would require us to solve

$a_{k-1}^2 + 2a_ka_{k+1}=2\lambda a_k,\quad k=1,\ldots,100,$

with indices taken modulo 100. As so often with these cyclic but non-symmetric expressions, this looks quite hard to solve. However, it turns out that by applying Cauchy-Schwarz to the vectors $(a_k),(a_{k-1}^2+2a_ka_{k+1})$ gets us a long way into the problem by classical means. Working all the way through is probably best left as an exercise.

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

IMO 2016 Diary – Part One

Balkan MO 2016 – UK Team Blog Part Two

Balkan MO 2016 – UK Team Blog Part One

Turan’s Theorem

EGMO 2016 Paper II

EGMO 2016 Paper I

Linear Algebra II: Eigenvectors and Diagonalisability

Linear Algebra II: Determinants 2

Linear Algebra II: Determinants 1

Lagrange multipliers Part Two