107年 - 107 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：線性代數與離散數學#147285

1. (15%) Answer the questions about the following graph. Is it a planar graph? Does it have an Euler circuit? Does it have an Euler path? Does it have a Hamilton circuit? Does it have a Hamilton path? Prove your answers.

(a) \( a_n = 8a_{n-1} - 15a_{n-2} + 8 \) with \( a_0 = 4 \) and \( a_1 = 12 \). (7%)

(b) \( na_n - (n+1)a_{n-1} = 1 \) with the initial condition \( a_0 = 1 \). (8%)

3. (12%) Consider the following relations on the set of integers, and answer the questions. Which of these relations are reflexive? Which of these relations are symmetric? Which of these relations are anti-symmetric? Which of these relations are transitive? Prove your answers.

$$\begin{array}{l} R _ {1} = \{(x, y) \mid (x - y) ^ {2} < 1 0 \} \\ R _ {2} = \{(x, y) \mid (x - y) \bmod 5 = 0 \} \\ R _ {3} = \{(x, y) \mid x \geq y + 3 \} \\ \end{array}$$

4. (8%) Answer the questions. How many one-to-one functions are there from a set with three elements to a set with eight elements? How many onto functions are there from a set with three elements to a set with eight elements?

(a) Show that they are linearly independent.

(b) Give the space \( \mathbf{S} \) which they span. What is the dimension of \( \mathbf{S} \)?

(c) Which matrices \( \mathbf{M} \) have \( \mathbf{S} \) as their column space?

(d) Give an invertible \( n \) by \( n \) matrix \( \mathbf{A} \). Show that \( \mathbf{A}\mathbf{v}1, \mathbf{A}\mathbf{v}2, \) and \( \mathbf{A}\mathbf{v}_3 \) is also a basis for \( \mathbf{S} \).

6. (10%) Factor the matrix B into B = LDLᵀ.

$$\mathbf {B} = \left[ \begin{array}{c c c} 5 & 5 & 0 \\ 5 & 7 & 2 \\ 0 & 2 & 9 \end{array} \right]$$

7. (10%) Project \( \mathbf{b} = \begin{bmatrix} 6 \\ 7 \\ 8 \\ 9 \end{bmatrix} \) onto the column space of \( \mathbf{C} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix} \). What is the projection matrix \( \mathbf{P} \)? What is the projection \( \mathbf{p} \)?

(a) Are all the pivots of \( \mathbf{D} \) positive?

(b) Are all the upper left determinants of \( \mathbf{D} \) positive?

(c) Are all the eigenvalues of \( \mathbf{D} \) positive?

(d) Is \( x^{T}Dx \) always positive except at \( x = 0 \)?

(e) Does \( \mathbf{D} \) equal \( \mathbf{R}^{\mathrm{T}}\mathbf{R} \) for a matrix \( \mathbf{R} \) in which all the columns are independent?