110 年 國立陽明交通大學資訊工程學系碩士班《線性代數與離散數學》

Consider the following real number:
$0.02468101214161820\ldots$

The 1st digit after the decimal point is 0; the second digit is 2; the 13th digit is 6; etc. What is the 1,000th digit after the decimal point?

Let $P=\{2,\{2\},\{\{2\},(2)\},(2),(2,2),\{2,(2),(2,2)\},\{(2,2),(2,2),((2),2)\}\}$.

How many elements are there in $2^P$ (which is the set of all subsets of $P$)?

What is the definition of an infinite set $W$?

Let $\mathbb{N}$ be the set of natural numbers. Assume we already know $\mathbb{N}$ is an infinite set. Let $S=\{k/2^n\mid n=0,1,2,\ldots;\ k\in\mathbb{N}\}$. Note that $/$ in this question is the division of real numbers. For example, $5/2=2.5$.

Prove that $S$ is an infinite set strictly according to your definition of an infinite set.

Assume $n\ge 2$. Let $A=\{x_1,x_2,\ldots,x_n\}$ be a set of (not necessarily distinct) natural numbers. Let $g=\gcd(x_1,x_2,\ldots,x_n)$ and $l=\operatorname{lcm}(x_1,x_2,\ldots,x_n)$. Assume $n$, $g$, and $l$ are appropriate fixed integers. Let $p=x_1x_2\cdots x_n$ be the product of the $x_i$'s.

What is the largest possible value of $p$ in terms of $n$, $g$, and $l? What is the smallest possible value of$p$in terms of$n$,$g$, and$l$?

How many integers between 1000 and 5000 are not divisible by 4, 5, or 6?

Let $a_k$ be the number of integer solutions of $x_1+x_2+x_3=k$, where $x_1\ge 2$, $1\le x_2\le 5$, and $0\le x_3\le 3$. Show the generating function for $\{a_k\}$.

Let $R_1$ and $R_2$ be equivalence relations on the set $S$. Prove that $R_1\cap R_2$ is an equivalence relation.

Please answer TRUE or FALSE for the following statement and give a concise explanation.

A simple graph is called regular if every vertex of this graph has the same degree. An $n$-cube, denoted by $Q_n$, is a graph that has vertices representing the $2^n$ bit strings of length $n$. Two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position. $Q_n$ is regular.

Please answer TRUE or FALSE for the following statement and give a concise explanation.

Let $V_n$ and $E_n$ respectively be the number of vertices and edges of $Q_n$, the $n$-cube. Then $E_1=1$, $E_2=4$, and $E_{n+1}=2V_n+E_n$.

Please answer TRUE or FALSE for the following statement and give a concise explanation.

The complete bipartite graphs $K_{2,3}$ and $K_{3,3}$ are planar.

Please answer TRUE or FALSE for the following statement and give a concise explanation.

There are exactly 2 shortest paths between $v_1$ and $v_2$ in the graph.

Please answer TRUE or FALSE for the following statement and give a concise explanation.

In the graph, there exists an Euler path from $v_5$ to $v_1$.

True or false. No need to justify your answer. No credit for unanswered questions. Incorrect answers will deduct the credit until zero point is earned in this section.

(correct: 1; incorrect: -1; unanswered: 0) For any square real matrix $A$, $A^T+A$ is always symmetric.

True or false. No need to justify your answer. No credit for unanswered questions. Incorrect answers will deduct the credit until zero point is earned in this section.

(correct: 1; incorrect: -1; unanswered: 0) For a square real matrix $A$, if $Ax=0$ has a non-zero solution, then $A$ is invertible.

True or false. No need to justify your answer. No credit for unanswered questions. Incorrect answers will deduct the credit until zero point is earned in this section.

(correct: 1; incorrect: -1; unanswered: 0) $\{(0,0,0)\}$ is the orthogonal complement of $\mathbb{R}^3$ in $\mathbb{R}^3$.

True or false. No need to justify your answer. No credit for unanswered questions. Incorrect answers will deduct the credit until zero point is earned in this section.

(correct: 1; incorrect: -1; unanswered: 0) Let $A$ be an $m\times n$ real matrix, where $m\le n$, with full row rank. $Ax=b$ has either 0 or 1 solution.

True or false. No need to justify your answer. No credit for unanswered questions. Incorrect answers will deduct the credit until zero point is earned in this section.

(correct: 1; incorrect: -1; unanswered: 0) Let $v$ be a vector in $S$ and $u$ be a vector such that $\langle u,v\rangle\ge 0$. Then $u\in S^\perp$.

True or false. No need to justify your answer. No credit for unanswered questions. Incorrect answers will deduct the credit until zero point is earned in this section.

(correct: 1; incorrect: -1; unanswered: 0) Let $A$ be a symmetric matrix. $C(A^T)$ and $N(A^T)$ are orthogonal complements.

True or false. No need to justify your answer. No credit for unanswered questions. Incorrect answers will deduct the credit until zero point is earned in this section.

(correct: 1; incorrect: -1; unanswered: 0) Let $u_1,\ldots,u_n$ be linearly dependent. Then $u_1,\ldots,u_{n-1}$ are linearly dependent.

True or false. No need to justify your answer. No credit for unanswered questions. Incorrect answers will deduct the credit until zero point is earned in this section.

(correct: 1; incorrect: -1; unanswered: 0) Let $U$ be a subspace of a vector space $V$. Then $(U^\perp)^\perp=U$.

True or false. No need to justify your answer. No credit for unanswered questions. Incorrect answers will deduct the credit until zero point is earned in this section.

(correct: 1; incorrect: -1; unanswered: 0) The null space of $A$ is equal to the column space of $A^TA$.

True or false. No need to justify your answer. No credit for unanswered questions. Incorrect answers will deduct the credit until zero point is earned in this section.

(correct: 1; incorrect: -1; unanswered: 0) Let $A$ and $B$ be $n\times n$ real matrices. Then $\operatorname{rank}(AB)\le \min(\operatorname{rank}(A),\operatorname{rank}(B))$.

Multiple choice questions and fill-in-the-blank questions. No need to justify your answer. No credit for unanswered questions. Incorrect answers will deduct the credit until zero point is earned in this section.

(correct: 3; incorrect: -1; unanswered: 0) Let $W$ be a subspace of $\mathbb{R}^n$ and $W^\perp$ denotes its orthogonal complement. If $W_1$ is a subspace of $\mathbb{R}^n$ such that $x\in W_1$, then $x^Tu=0$ for all $u\in W^\perp$. Justify whether the following statements are true or false:

(i) $\dim(W_1^\perp)\le \dim(W^\perp)$

(ii) $\dim(W_1^\perp)\le \dim(W)$

(iii) $\dim(W_1^\perp)\ge \dim(W)$

(iv) $\dim(W_1^\perp)\ge \dim(W^\perp)$

(correct: 3; incorrect: -1; unanswered: 0) Let $A$ be a $7\times 5$ matrix with $\operatorname{rank}(A)=5$. Justify whether the following statements are true or false:

(i) There exists at least one $b\in\mathbb{R}^7$ such that $Ax=b$ has infinite number of least squares solutions.

(ii) For any $b\in\mathbb{R}^7$, $Ax=b$ has infinite number of solution.

(iii) There exists at least one $b\in\mathbb{R}^7$ such that $Ax=b$ has a unique least square solution.

(iv) For any $b\in\mathbb{R}^7$, $Ax=b$ has a unique solution.

(correct: 3; incorrect: -1; unanswered: 0) Let

be the least-squares solution that minimizes $\|Y-XB\|^2$, where

Find the values of $(i)$ and $(ii)$.

(correct: 3; incorrect: -1; unanswered: 0) Let

be the orthogonal projection of $b$ onto $u$, where

Find the values of $(i)$ and $(ii)$.

(correct: 3; incorrect: -1; unanswered: 0) Let

be the closest point to $y$ in the subspace $W$ spanned by $u_1$ and $u_2$, where

Find the values of $(i)$, $(ii)$, and $(iii)$.

Determine whether the following statement is true or false:

If $A$ is an invertible matrix, then $\det(A^{-1})=[\det(A)]^{-1}$.