Monday 8 April 2013

Linear algebra

Here comes another big project.

As you may have noticed I have another blog writing some basic analysis notes but that turns out to be not very efficient. This time I switched the topic (as requested by whom I'm writing for) to linear algebra, using pure PDF form and hope you will like it.

I do not aim for rigourness very much since she(?) is not a professional in mathematics. Instead I try to describe the big picture on how the linear algebra work on system of linear equations and the nature of matrices. At later section I will try to describe some linear transformations and eigenvalues associated.

Recently it's half-finished and click me to access the note. The topics covered now is the basic stuffs only:

Topics:

Ch.1 System of linear equations
Ch.2 Vector
Ch.3 Matrices
- Matrix operations, multiplication, elementary matrices, inverses
Ch.4 Determinants
- Determinants and system of linear equations, cramer's rule, factorization
--------------------Unfinished:
- Linear independence, orthogonality
- Rank, spaces and dimension
- Vector spaces
- Eigenvalues
- Linear transformation
- Decomposition
- Linear programming

Version:

v0.5.0 8 Apr, 2013

If you find any error, in any forms (including grammar or mathematics), please kindly tell me to fix them.

Wednesday 3 April 2013

Friendwheel

Errrrrr three months from my last entry...

Anyway if you haven't heard of friendwheel, a facebook apps that generates the graph of friendship links of all your friends:


(I blurred the names of my friends for privacy. These blurred pixel looks awesome right?)

In general, they put similar friends closer (this is how the wheel works --- grouping in similar colour)

However as you can see some of the points are emitting a lot of linkage far from the neighbouring group. It turns out that their alogarithm is not very effective.

Definition. Distance between two points are defined by (number of points between them)+1

Definition. Circular n-tuple (a_1,...,a_n) is n numbers in order, and a_1 is supposed to be the next term of a_n. Due to the cyclic structure, it is equivalent to (a_2,a_3,...a_n, a_1) and so on.

Definition. Given a graph G = (V,E), the optimal permutation is a circular |V|-tuple where the tuple is the permutation of vertices so that sum of distance between any two linked vertices is the minimal.

Definition Given a graph G = (V,E). Optimal distance is the sum of distance between any two linked vertices.

The optimal permutation is not necessarily unique. For example consider:

G = (V,E); V = {1,2,3,4}, E = {(1,2),(3,4)}, then both (1,2,3,4) and (1,2,4,3) are optimal permutations with optimal distacnce 2.

Now the problem is, how should we reduce the sum of distance given G and an arbitrary permutation of V? I'll propose a heuristic here:

begin;
local_min_reached = FALSE
while not local_min_reached:
---swapping = FALSE
---for i in 1 to n:
------check if swapping a_i and a_{i+1} reduces sum of distance
------if yes then swap the two vertices
------swapping = TRUE
---if swapping = FALSE:
------local_min_reached = TRUE
return permutation of edges.

I'm so lazy to calculate its preformance ratio as well as other stuffs since it would take me quite a lot of time to do the simulation (like my research topic), but I'm sure that this one is qutie near to the optimal solution. I have no idea to construct G so that the procedure stuck at local optimum and fail to reach the global optimum with the above alogarithm.

Any idea?