Chapter 6: Exercises

Part 1

  1. 請寫一個 MATLAB 程式碼 testMat01.m,請依下列步驟進行此作業:
    1. 使用 randn 指令產生一個 10×10 的矩陣 A。
    2. 計算 B=(A+A')/2。請注意,B 一定是一個對稱矩陣。
    3. 計算矩陣 B 的固有向量 e1, e2, ... e10。
    4. 驗證在 i 不等於 j 的情況下,ei 和 ej 的內積必定為零。
  2. 我們可用數學證明:一個方陣的行列式值會等於其固有值的乘積。請寫一個 MATLAB 程式碼 testEig01.m,隨意產生 10 個 100×100 的方陣來驗證上述定理。
  3. 我們可用數學證明:一個方陣的主對角線的元素和,會等於其固有值的和。請寫一個 MATLAB 程式碼 testEig02.m,隨意產生 10 個 100×100 的方陣來驗證上述定理。
  4. Please use 3 lines of MATLAB statements to solve the following simultaneous linear equations: $$ \left\{ \begin{matrix} x+y+z=1\\ 3x-y-3z=4\\ x+5y-9z=0\\ \end{matrix} \right. $$
  5. 請寫一個 MATLAB 程式碼 lse01.m,使用 MATLAB的「左除」找出一點 P,使得 P 到下列三條直線的距離平方和為最小: $$ \left\{ \begin{matrix} 2x-y = 2\\ x-2y = -2\\ x+y = 1\\ \end{matrix} \right. $$ 請問 P 值為何?此時最小距離平方和是多少?
  6. 請寫一個 MATLAB 程式碼 lse02.m,採用 MATLAB 的「左除」運算,找出下列聯立方程式的最小平方解: $$ \left\{ \begin{matrix} 3x+2y = 1\\ x+3y = 4\\ 4x+2y = 3\\ x-y = 6\\ \end{matrix} \right. $$ 此時最小平方誤差是多少?

Part 2

  1. Definition of eigenvalues and eigenvectors: What is the definition of eigenvalues and eigenvectors of a square matrix A?
  2. Formula for eigenvalue decomposition: What is the formula for eigenvalue decomposition? (Please clearly define your notation.)
  3. 試用 MATLAB的「左除」運算,找出最接近下列五點的最小平方三次多項式:
    (1, 5) (2, 3) (3, 4) (4, 7) (5, 2)
    請畫出此多項式及這五點資料。(請使用 MATLAB的「左除」或「反斜線」,而不要直接使用 polyfit 指令。)
  4. Sum of squared distances between a point and multiple planes: 請使用 MATLAB的「左除」找出空間中的一點 P,使得 P 到下列 4 個平面的距離平方和為最小: $$ \left\{ \begin{matrix} 2x-y+2z & = & 2\\ x-2y-2z & = & -2\\ x+y+z & = & 1\\ z & = & 5\\ \end{matrix} \right. $$ 請問 P 值為何?此時最小距離平方和是多少?
  5. Eigenvalue of same-column-sum matrix: Suppose that a square matrix A has its column sums all equal to k. Prove that k is an eigenvalue of A.
  6. Power method to compute page rank: As described in our slides, we can use the power method to find the page rank of a given connectivity matrix. That is, we can repeat $\mathbf{x}=A*\mathbf{x}$ until $\mathbf{x}$ converges to find the page rank, where $A$ is the transition probability matrix derived from the connectivity matrix. Write a function pageRankByPower.m to return the page rank, with the following usage:
    [pagerank, iterCount]=pageRankByPower(G, p),
    where
    • G: the given connectivity matrix
    • p: the given probability of following a link in a page
    • pagerank: the returned page rank
    • iterCount: the iteration count of the power method
    More specs are as follows:
    • Note that you can only use the power method to implement this function.
    • The initial guess of the page rank should be a probability vector of uniform distribution.
    • The maximum iteration count is 100. Once the maximum iteration count is reached, the current page rank is returned immediately.
    • The iteration stops whenever max(abs(pr-prprev)) < eps, where pr is the current page rank and prprev is the page rank obtained at previous iteration.
    You can download the p-file pageRankByPower.p to test your function. Here is a test script with several test cases:

    Example 1: 06-線性代數/pageRankByPower01.mG=[0 0 0 1 0 1;1 0 0 0 0 0;0 1 0 0 0 0;0 1 1 0 0 0;0 0 1 0 0 0;1 0 1 0 0 0]; p=0.85; [pageRank1, iterCount1]=pageRankByPower(G, p) G=[1 0 0 0 0 0 0 1 0 0;1 1 0 0 0 0 0 0 1 0;0 1 1 0 0 0 0 1 0 0;1 0 1 0 0 0 0 0 0 0;0 1 0 0 0 0 1 1 1 0;0 0 0 1 0 0 1 0 0 0;0 0 0 0 0 1 0 0 0 0;0 1 0 0 0 0 0 0 0 0;1 0 0 1 0 0 0 0 0 0;1 1 0 0 0 0 0 0 0 0]; p=0.9; [pageRank2, iterCount2]=pageRankByPower(G, p) pageRank1 = 0.3210 0.1705 0.1066 0.1368 0.0643 0.2007 iterCount1 = 64 pageRank2 = 0.0541 0.0929 0.1110 0.0899 0.1683 0.1417 0.1578 0.0470 0.0805 0.0567 iterCount2 = 74

  7. Ranking of sports teams: In this assignment, we shall use the concept of Google's PageRank for team ranking. During a sports season, we have four teams with the following result, with "m-n" indicating that there are m+n games between two teams, with m winning games for the left team and n winning games for the right team. (For instance, 3-1 between teams A and B indicates that A has 3 winning games while B has 1.)

    We shall use the following steps to explain how to find the strength (or team rank) of each team.
    1. We can use a matrix GD to respresent the result of "difference in winning games": GD = [ 0 2 1 0 -2 0 -2 -2 -1 2 0 0 0 2 0 0]; where GD(i,j) is the no. of difference of winning games between team i and team j. For instance, GD(2,1)=1-3=-2, while GD(1,2)=3-1=2. (Note that GD is anti-symmetric.)
    2. We want to find a voting (or recommendation) from each team to the others. Since the voting should be positive and bounded, one way to achieve this is by using a sigmoidal function: A = 1./(1+exp(-GD)); A(1:5:end)=0; Then we can have the voting matrix: A = 0 0.8808 0.7311 0.5000 0.1192 0 0.1192 0.1192 0.2689 0.8808 0 0.5000 0.5000 0.8808 0.5000 0 where A(i,j) is the voting from team j to team i. Note that:
      • A(i,j)=0.5 if two teams have the same number of winning games, such as A(4,1).
      • A(i,j)<0.5 if team j is stronger than team i, so team j is giving weaker vote to team i. For instance, A(2,1)<0.5 since team 1 is stronger than team 2 by 2 games.
      • A(i,j)>0.5 if team j is weaker than team i, so team j is giving stronger vote to team i. , such as A(3,2)>0.5 since team 2 is weaker than team 3 by 2 games.
    3. Next, we can convert the vote matrix A to be a transition probability matrix by dividing each column by its corresponding column sum. This can be achieved by B = bsxfun(@rdivide, A, sum(A)); Then we have the transition probability matrix B, with each column summing to 1: B = 0 0.3333 0.5414 0.4467 0.1342 0 0.0883 0.1065 0.3028 0.3333 0 0.4467 0.5630 0.3333 0.3703 0 By following the same concept as Google's PageRank, the team rank x should satisfy $Bx=x$. That is, the team rank x is an eigenvector of matrix B with corresponding eigenvalue of 1.

    By following the above reasoning steps, write a function myTeamRank.m to return the team rank, with the following usage:

    teamRank=myTeamRank(GD),
    where
    • GD: the matrix of winning game difference
    • teamRank: the returned team rank vector to show the strength of all teams
    You can download the p-file myTeamRank.p to test your function. Here is a test script with several test cases:

    Example 2: 06-線性代數/myTeamRank01.mGD=[0 2 1 0;-2 0 -2 -2;-1 2 0 0;0 2 0 0]; teamRank=myTeamRank(GD) teamRank = 0.3186 0.0998 0.2693 0.3123

    Hint: Note that it is almost impossible to have an eigenvalue of 1 exactly after numerical computation. Instead, you can find the eigenvalue of maximum magnitude instead.

MATLAB程式設計:進階篇