Monday 21 December 2015

LA2, second attempt on my linear algebra notes

Let us call it LA2. My previous attempt [the 1.5LA] looks horrible 2~3 years after producing it. Hopefully it is better this time. I'm sure that it will as one's understanding on these elementary topics always improve with your understanding on advanced topics, like functional analysis, matrix analysis...etc.

Click here for the notes

Well I compiled this by picking different bits from my revision notes then some careful fixes and some effort to make it smooth. The beginning two-third is a basic linear algebra course, and the last one-third is an advanced but interesting topic to cover: linear programming.

My general principle to arrange the contents is to solve three main problems: to compute the inverse of a matrix, the geometric implication of linear transformations, and the duality principle in linear programming. Some external guidance are also taken, like the classic Linear Algebra from S. Lang.

Multiple references are taken, see p.3 of the text. I've taken [copied] some exercises from those references as well.

Ch.1 Basics: vector and matrix arithmetic
Ch,2 Linear system: reduction, independence, dimension
Ch.3 Geometry I: orthogonality, projection
Ch.4 Determinants: implication in lower dimensions, elementary matrices, matrix inverse, Cramer's rule
Ch.5 Abstract vector space: axioms, function space, inner product space
Ch.6 Linear Transformation: coordinate mapping, change of basis
Ch.7 Eigenvectors: diagonalization, applications
Ch.8 Special operators: Hermitian, unitary operators, orthogonal diagonalization, spectral decomposition
Ch.9 Geometry II: affine space, convex sets, cones
Ch.10 Polytopes and polyhedrons: V-H characterization, Fourier Motzkin elimination
Ch.11 Linear programming: Farkas Lemma, separation, simplex, duality

It was not the main motivation to get the old 1.5LA revamped, but actually I'm writing this for one of my dear friend who is studying computer science who is getting stuck with them, and I hope that there will be more readers other than him :)

And, merry Christmas.

Chris, Dec 2015

Wednesday 4 November 2015


Baseball oh baseball.

Another wonderful season has just ended. A late congratulation to Lamigo monkeys who gave a blessed display in G5-G7, the no hitter has been stunning and it was unimaginable that he had just played as a relief pitcher in the last game. Whilst on the opposite side of the globe, Cubs fans may have to wait another hundred years...

Baseball is the last sport that I've been paying attention to its professional leagues, other than football. That's a nice complement out of the football season after all, but that isn't the end of the story. They are completely different in nature.

Football, I am not sure if all of you would agree, is a chaotic process in nature. From the extremely wide varieties of tactics that leads to rigidity in substituting players, to a full dynamic process during the game, has made the whole season full of dependence and has random events leading all the way through. That doesn't seem to be obvious because every particular professional games has their strategy cautiously set up and ruthlessly executed, and being a full dynamic game the advantage accumulates --- and become decisive in the game. However looking the game in a more macroscopic way tells a different story. I learned that after following football for 10 years, and I bet it also took Abramovich also 8 years to realize that --- in 2012 --- the best team is not always going to win the champions league --- the phantom goal in 2005, the penalty showdown in 2006 and 2008, the Stamford Bridge massacre in 2009...and the against-all-the-odds display in 2012. It's the accumulation from the whole season that makes the slightest edge in the later stages of the Champions League. [Just a famous quote from zonal marking that I do agree quite a lot: semi-final of the champions League is always the most exciting, unpredictable, technically rich game in the whole tournament. And for me, being the semi-finalist is all about team strength and going any further requires a steel of mind with brilliantly delivered tactics, and loads of luck.]

Baseball however, has it quantity overwhelmed so that the game boils down onto data that really matters. Batter faces all sorts of pitchers and pitcher faces all kinds of batters, on a daily basis so the data representing their efficiency shows high correlation with their real performance. AVG [well some may think that being not very useful, especially for Moneyball fans], OBP, OPS --- accurately measures how efficient they score; ERA, H/9, WHIP --- predicts how likely pitches are going to allow runs. Whether it is a 100 mph 4-seam blitz, or a nasty curveball --- it does not matter --- in long run. Teams with proper farms may substitute a player by another without much difficulty, perhaps a drop of .05 in OBP, no one is really untouchable statistically. Drafting and exchange market, FA system, money and players lurking around --- definitely not the so called 'traditional' way in sports industry huh? But that's not the reason I love baseball. Taking a closer look into the game every single duel between the batter and the pitcher must be the star of the game. Look at the mind battle between them, their logical reasoning and physical reaction [baseball is 90% physical, and the other half is mental.], how can't you love that?

Two sports from two different culture, starring two different aspects in nature. I don't expect many to follow both as I do, but that will be on my recommended list seriously.

Oh, of course professional leagues aren't all of the sports available. We always have something called a union --- once again big, big congrats to the All Blacks, who again gave an astonishing display throughout. Hopefully I will have the honor to watch it live in Japan, 2019.


Thursday 25 June 2015

Math Girls; Galois theory

It is never easy to teach someone else, and it is even harder to teach others an advanced topic. In university the ideal case would be giving the motivation during the lecture and students do the rest by themselves during self-study or supervision. But, if we really ought to teach someone from the very beginning, what would be the best choice? This is of course a very complicated question and for sure I cannot give the answer here.

My way to do it is to follow the historical treatment - doing what those mathematicians did hundreds of years ago. What they did, why they did so --- this is exactly what helps students to understand the mechanism behind a topic. Landau styled definition-theorem-proof aren't bad, they are just a bit too hard for those understanding ability not being the best.

Based on the above I have found a series interesting, the Math Girls by H.Yuki. There are 5 vol. available in Chinese and Japanese, and the first 3 vol. are published in English. Such series perfectly illustrates the above. Topics delivered via conversation and story-telling, and by merging yourself into the discussion the history behind will simply push you all the way through to the end of the journey.

It is mostly easy for senior secondary school students --- mostly refers to the most part of the book. It starts basically from stretch and the difficulty gradually increase, but it is usually tolerable till the last chapter. Nonetheless one will be able to appreciate the theory without precisely understanding the technical procedures.

A few months back I've just finishing reading his 5th book of the series on Galois theory. One of the clear motivation behind the theory is the irresolvability of quintic equations in radicals. This is of course a very hard question, that had puzzled mathematicians for three hundred years, until a genius called Galois came up with his genius idea (that no one can realize till some years later) a day before his duel, where he lost and died. It was a sad story (he is one of the many French mathematicians that died in weird ways), but this is not the main point --- where was his idea came from?

It is the permutation of roots.

Classical algebra books will illustrate this via quadratic equations, cubic equations and quadric equations. However this is not very clear under numerical examples beyond the quadratic case. In particular, Cardano's solution for cubic equation is fairly unpleasant. There are so many radicals added --- which one gives an extension? Which one does not? What is the degree of extension?... When I first tried to read through graduate texts on Galois theory I kept asking questions like this to myself and got myself puzzled.

In the book they put some effort analyzing those equations in an elemental way. No groups, no fields --- this is also what mathematicians did in the past. I personally found that extremely useful by the end of the day, and I loved that book.

It might be a bit more approachable using modern language than Galois' first thesis, but it does not change the fact that his thesis is showing the core idea of the whole theory, so following the historical treatment it would be the best for one to follow the thesis to explore the elemental part of his theory. That was not obvious until the very last bit [Kummer extensions, main theorem for quintic equations], so I will try to fill that gap here, if I have time, probably in the coming entry.

And yeah, for those who are interested in mathematics [in particular if you know how to read Chinese or Japanese], I would sincerely recommend that to you.


Theorem. $x^5-16x + 2 = 0$ has no radical solution over $\mathbb{Q}$.


Friday 5 June 2015

An interesting sum

Here is a probability problem recently: Suppose you want to make a system that a player eventually wins --- this is pretty straightforward in the theoretical sense because under a sequence of independent trials with winning rate $p>0$ it is always possible to win eventually.

We may model the problem as a roulette problem, where we have $N$ balls inside a box in which one of them is special.

The simplest model is the geometric model --- we put the non-special ball back and retry the whole process. It follows a geometric distribution with expectation $\frac{1}{p}$. But this is far too slow, and it has a large variance with $p$ is small.

Monday 18 May 2015

A trip to South Island, New Zealand (5): Te Anau

Welcome back. I feel like I should get this done as soon as possible because I'm starting to forget some details in it, but let's deal with Te Anau, another early settlement in the South Island.

It had been more and more rural as we headed further south. Fiordland is the SW-most region of the country and is merely inhabited. Te Anau is a small town besides the Te Anau lake and acts as an gateway of the Fiordland national park. The tramping track here looks even harder comparing with the one in Mt Cook and we didn't have time to have a go -- but it is quite dull here otherwise. In fact, the argue over the pronunciation of the town's name is even more interesting.

Sunday 22 March 2015

Algorithms on partitioning

Hey everyone do you sense anything different? Well the Project Euler counter breezed from 166 to 175 in these one or two days, and it's like I can reach 200 or 225 without much difficulty. The main reason is that a new difficulty rating is out (it may not be new for you if you visit the site frequently though), and we can access to relatively easier later numbered question easier.

In fact many of them relies on the same searching technique or a number theory let's look at one of the classic algorithm and its variation:

We start from a classical example: In how many ways we can partition a number $n$ into sum of integers? (Don't cheat by looking at the OEIS!)

Sunday 8 March 2015

A trip to South Island, New Zealand (4): Tekapo

Without much resources except the land itself, the exploring trail along the Southern Alps 150 years ago remained to be the major populated area in the South Island. Tekapo is another early settlement beside the lake of the same name --- just as the triple point of matters, we have the triple point of New Zealand here --- the intersection of calm waters, great mountains and clear sky.

Thursday 12 February 2015

Feb 12 2015

Welcome back. Allow me to update the blog here:

The entry counts had been declining over the 2 years partially due to exhausted math and other high school academic topics, but also some side dishes like MUG-games related entries, or even self creation.

In 2015, or at least in the first half of 2015, I decided to push my productivity a bit further and entries on the following topics are scheduled:

1) My trip in South Island of New Zealand, probably 3 or 4 more entries.

2) A sequel on my card collection problem. I have to admit that I am now a big fans of a particular card collection game (and obviously it has been a trend on the smartphone platform!). This time we will look at the problem on the other aspect: completeness of the collection.

3) I finally managed to find some of the original copies of my old notes since my previous ftp server closed without any notice beforehand. I will update them someday onto my new site.

4) I may not be very good at arts but I definitely enjoy them a lot. Among them Literature will the the easiest to be shared among them. I will talk about books, not on a specific ones but a series of related books. This will be done in Chinese, of course.

Saturday 24 January 2015

A trip to South Island, New Zealand (3): Mt. Cook

Mount Cook is the highest mountain in New Zealand and remains to be one of the most amazing scene there. You can simple leave everything behind and spend a few days here to enjoy the grand nature.

Taking around 4 hours of bus trip from Christchurch we planned to stay here for another two days. We walked along various tracks which sum up to 16km and every centimetre is well-deserved to have a go.

Wednesday 7 January 2015

On card drawing problem

Faithful greetings here and wish everyone to do well in 2015. Before I continue to write about my journey, let's consider a game-related modelling problem here.

Recently there are a series of electronic games mainly on mobile platforms that collects various cards for the game system. There can be a lot of variation on the game like tower defence, card battling, action shooting etc. but these aren't really important. They can all characterized to be a card collection game (CCG).

What elements must a card collection game contain? A free way to obtain cards through events, and a paying way to obtain cards, that we call it an invocation. A basic model would contain a card pool where every time a card is chosen, at a certain probability and given to the player.

In order to attract the players to spend further, we can usually find some alternate option to invoke cards that apparently a better option. A typical way is to guarantee a rarer card when the invocation is done in a larger batch. Without a further assumption in the rate of appearance for the rare cards we ought to see which option is better.

In this entry we will simply our model to two types of cards: common and rare cards. A binary model would allow binomial distribution and make everything easier.

Since the number of cards is finite, and of course countable, the following calculations will be done with respect to discrete distributions.