如何發表新文章？

即日起，欲申請在此Blog參予討論的同學，亦可向線代離散助教(wynne)申請開通發表文章之權限。

申請流程如下：
1. 請準備好您的google帳號
2. 請以該帳號將您的

• 姓名、
• 補習班證件字號 （一般學生）或身份證字號（TKB學生）

等資料，寄給線代離散助教(wynne)。

請於申請日的1~2天後至您的帳號信箱收取權限開通信函；在確認權限開通之後以您的google帳號登入，即可於Blog首頁的右上角看到發表新文章之按鈕。謝謝配合！

請教一題交大100年資結(離散)的問題

Let d and k be two non-negative integers, where k > d >= 0. A dk-binary sequence is a binary sequence that satisfies the following two constraints：
(a) d constraint：two 1's are separated by a run of consecutive 0 of length at least d
(b) k constraint：any run of consecutive 0's is of length at most k.
for example, 010010001001 is a dk-binary sequence of length 12 width d=0 and k=3. Let n indicate the length of dk-binary sequence

(47) Given n=6, d=0, k=6, then how many dk-binary sequences are there? a.8 b.16 c.32 d.64 e.128
(48) Given n=10, d=4, k=5, then how many dk-binary sequences are there? a.8 b.6 c.12 d.10 e.11
(49) Given n=14, d=1, k=14, then how many dk-binary sequences are there? a.81 b.160 c.821 d.987 e.1024

(47)我當場有想出來，就2^6答案d，(48)好像推不大出來，但答案是e(49)剛剛想出來，就不能連續1，Fibonacci number 答案d

想請問48怎麼推導會比較好？

[離散] 99台大電機

If f : X→Y is a one-to-one and onto function, and Y is a proper subset of X, which of the following statement is correct?

(a) X must be countably infinite
(b) Y must be countably infinite
(c) X must be infinite
(d) The cardinality of X is lager than Y
(e) None of the above

答案是c
想請問這題在考什麼概念呢？為什麼答案是c？完全沒有頭緒…
感謝！

請問有快一點的作法嗎？

請問下面是否有做錯？

100台大電機第一題

題目沒記錯好像是這樣：

求滿足上式的所有n值

用邊長為一的正方形是可切出n=1,4,6,7,8

再建構出9=4+6-1,10=4+7-1,11=4+8-1,12=6+7-1,13=7+7-1, ...

似可用數學歸納

請問證明怎麼寫比較好？

請問一個笨問題

算內積從-1積到1，要算角度，如果算出來是cosθ = 0，也就是90度和270度，是寫90度就好，還是2個都寫？

99中央離散

第10題題目給了A={1,2,4,6,8,10}
而B給了B=A^2
請問B裡面有什麼
我好像沒看過集合取平方
是A的所有元素的平方嗎?
先感謝助教了

政大考古題

(不確定題意)想請問這題是要求x^tAx中的A嗎?

我的算法是|subset|=1,2....9分別求算，請問有比較快的想法嗎?

我把true table畫出來沒有一個是一樣的，請問這該怎麼解?

(還有幾題是非題)

謝謝助教

交大100年線代的問題

Any two finite dimensional vector spaces with the same dimension are isomorphic.
這題居然是true…isomorphic不是要線性，1-1且onto嗎？…維度相同不見得線性且1-1、onto吧…太不可思議了…

rank

請問這題求RANK，有特別的求法?

答案錯?

求正交對角化，得三根 6, 0(重根)
6帶入得，令X3=s ,s* [-2, -1, 1]^T......答案寫 s*[2, 1, -1].....有差嗎?
0帶入更奇怪，2X1+X2-X3=0 .......答案寫c1[0, 1, 1]^T+c2[1, -1, 1]^T...c1 c2 不知道是指哪個
我自己解如下
X2= - 2X1+X3，X1=s X3=t 得 s*[1, -2, 0]^T+ t * [0, 1, 1]^T
X3= 2X1+X2，，X1=s X2=t 得 s*[1, 0, 2]^T+ t * [0, 1, 1]^T
沒有一組根答案相同，解答的答案如何求出來的? 還是答案錯了
-------------------------------------------------------------
還有另一題
2x-y+3z=0....求vector space
解：
y=2x+3z
令X=s, Z=t
s*[1, 2, 0]^T+ t*[0, 3, 1]^T.....我的答案
解答寫c1*[2, 1, 0]^T+ c2*[0, 3, 1]^T c1 c2也是不知道指哪個
--------------------------------------------------------------
請問是答案寫錯了??? 還是我哪邊算錯

正交對角化

特徵根為 -3 和 1，當 -3 的特徵向量沒有問題但是

特徵跟 1 可以求出

X1=X2-X3
令X2=s , X3=t
[s-t, s ,t]^T=s[1, 1, 0]^T+t[-1, 0, 1]^T...............A
--------------------------------------------------------------
X2=X1+X3
令X1=u , X3=t
[u, u+t, t]^T=u[1, 1, 0]^T+t[0, 1, 1]^T...............B
--------------------------------------------------------------
這兩種解的單範正交不同，不為單範正交要做Gram，單範正交要為1
A=1*(-1)+0+0=-1
B=0+1*1+0=1
可是A不為單範正交，B為單範正交，到底做不做Gram........還是單範正交可為 -1 ???

--------------------------------------------------------------

還有特徵根為 1 時，因為變數位置取的不同，有三組特徵向量，就用A B兩種來看，要寫哪組???

離散-著色多項式&機率

用聯集的方法 ,算出來為λ*(λ-1)*((λ-2)^3)

但覺得怪怪的

想請問著色多項式是唯一嗎?

因為自己對圖上λ

先對右上角上λ

最上面λ-1

左下角λ-1

其他兩點λ-2 , λ-2

結果為λ*((λ-1)^2)*((λ-2)^2)

是我哪邊搞錯了嗎

6. (10%) A pair of fair dice is continuously rolled until either a 1 or a G

appears at which point the experiment stops. What is the probability

that the experiment was stopped not because of 1's appearance?

結束的情形可能為 (1,x), (x,1),(6,x) (x,6) 其中x=1,2,3,4,5,6 總共有20種可能

其中去掉包含1的可能 (1.1) (1.2) (1.3) (1.4) (1.5) (1.6) (2.1) (3.1) (4.1) (5.1) (6.1)等11種

所以1不出現的情況下結束的機率為 9/20

7. (10%) Suppose P balls are distributed at uniformly random into N

boxes. Let Xi be a random variable defined by Xi = 1 if box i is

einpty and Xi = 0 otherwise. Compute E(Xi), the mean of Xi. What

is expectation of the number of einpty boxes after these P balls were

distributed.

請這題的機率要怎麼設呢?

請各位高手 與助教指點迷津

這題看不懂耶,是有限狀態機 還是霍夫曼??
該怎麼做阿??

台大97

Sorry 我知道前面有人問過
但我實在不懂 為什麼這樣算就能求得最小值

將下面化成|r| + |s| + |t| 的目的是?

然後2的地方
那個不等式我看的董
但我不知道求出來之後 為何就能求出最小值

因為<= 是保證 左邊大於右邊
但不保證 算出來的值左邊會是 f(r,s,t) 所組合的 Maximan

orthogonal set

 請問orthogonal set為線性獨立嗎?

因為模考中有一題
Let W be a subspace of R^n. If W=span{x1,x2,x3} with {x1,x2,x3} linear independent, and if {v1,v2,v3 } is an orthogonal set in W, then {v1,v2,v3} is a basis for W.  -->False.


請問是為什麼呢?難道是因為v有可能為0
但我不是記得orthogonal set為線姓獨立嗎? 還是說還要加個擁有非0元素之orthogonal set才為獨立?

謝謝

Commutative

  

這題答案請問是(A) (E)嗎? 因為成大這題考是考在單選題，不知道是我算錯還是答案錯 Orz...

(A)正確有 4* 4^12

            

(E) 正確有4^10 

關於(E) commutative F(A,A)不一定為A吧?

謝謝

一些考古

第一張圖:第二章圖是答案 我這樣算對嗎?

第三張圖:

d看不太懂題目 猜false (考邏輯?)

g的圖畫在右邊 所以是fasle?

第四章圖:
第五題看不懂 第四題不會證 冏

最後一張 第一題 不知道要怎樣才有R的關係 題目是說 ((a b),(b,a))

這樣具有symmertric的意思嗎?

第二題 答案是我用紅色圈起來那樣嗎?

問題蠻多的 不好意思 麻煩大家了

助教您好...想問題庫T2 P2-62 另加一題...

98台大電機
Which of the following statements is false?

a. The union of a countable number of countable sets is countable

d.The sets A and B have the same cardinality if there is one-to-one correspondence from A to B

請問這兩個不是都錯嗎?
我的理解是
a.可數個聯集 可是N(自然數)也是可數集，但是無限
所以我如果取無限個來聯集，不是就不可數了嗎?

d.應該要1-1 且 onto 才符合定義不是嗎?

這題答案是全部true
其他兩個較沒問題所以我就沒列了..

前面有一題

問說from 左邊level i 到右邊level j可有幾種path
我是想說2^i * 2^j
可是助教解的2^j還有除一個2
那是什麼意思呢?

麻煩助教了
感恩

trace

我想請問一下tr( (AB-BA)(AB-BA)^t ) =0 => AB-BA=0 是怎麼推導出來的呢?
還是說trace(A * A^t) = 0  implies A=0 呢?

cosA

請問 我用 PDP^-1的方法
算不能嗎? 我算出來的答案跟他都差 每項都只有cos1 項而已

我看離散課本 sinA 他是這樣算的呀0.0

cos(A)= PDP^1 = [ 3 2 ] [ 0 0 ] [ 1 2 ]
[ -1 -1 ][ 0 cos 1] [ -1 -3]

99交大數學

線代
第二題
a.是說 此矩陣的eigenvalue是矩陣行數 倍數的意思嗎?
可對角話當然dim(ker(A-λI))不同的λ 相加維度會是N維
不知道跟題目有什麼關係orz

b.我只知道A為可逆矩陣 第二小提意思是要我A可逆的條件去證她嗎?
pf:
因為A為可逆=>行獨立
A[a1v1 a2v2 a3v3.......]
因為可逆*可逆仍為可逆
所以[Aa1v1 Aa2V2........]
其rank也是n故得證

這樣證明OK嗎?

第4題 d:F e:T f:F g:T 這樣答案對嗎?
g之證明如下
因為(I-A*A^T)X為N(A^T)的向量
A^T(I-A*A^T)X
=>(A^T-A^T*A*A^T)X
=>(A^T-A^T)X=0
這樣證對嗎?

第5題的d 他是要我用N去表示遞回嗎?
所以直接寫費氏數的版本就OK囉?@@
e 不知道怎麼算 懇請幫助

以上題目麻煩大家解答 感恩

模擬考一題:TREE

A full m-ary tree T has 81 leaves and height 4.Give the upper bound and lower bound for m.

想請問畫紅線那段是怎麼導出來的?

請教有關線性映射的問題

Let T(v) be a transformation that projects v onto the line passing through (0,0) and (1,-2). let w=(-5,10) then T(w)=(5,-10). false
如果是一般的投影在x或y軸就直接乘一個投影矩陣就好了，現在是投影在某一條線，線的方程式算出來是y=-2x，再來就不知道要怎麼算了，麻煩幫忙解答，感謝

離散
P6-69 定理6-9
先造一條maximal path
證到後面發現其實是cycle，還有點可再加入並去邊成為更長路徑
這樣是否與一開始造的極長路徑矛盾？

直和的問題及空集合具反身性嗎?

1.請問一下，若V = W1 + W2 = W1+ W3，且W1與W2為V之直和，W1與W3為V之直和。
那W2=W3嗎? 若不等於，可以舉一個反例嗎? 謝謝~


會有這麼一個疑問是因為在Linear algebra一書中，看到一行:

2.請問空集合，具reflexive嗎?
(因為我上課抄空集合不具reflexive，事後想想覺得怪怪的，是不是我抄錯?)

3.If A is an n*n real matrix such that x^t A x =0, for all in R^n, then A=0。

Ans: False
可以請助教舉一下反例嗎? 還是說x^t A x =0 可以有什麼定理可用? 我現在只知道A應為nilpotent matrix，謝謝。

離散

T/F
the poset(N,|) of non-negtive integers N under dividibility relation | is a lattice
but is not bounded since it has no greatest element
答案是T
請問為什麼(N,|)是絡??
0要擺在HASSE DIAGRAM的哪裡

一些電機考古題

(2)
(B)
Propositional logic does not have a sound and cmoplete deduction system.
是指說 像 (A | B) & (A | C) = A | ( B & C)
這種簡化的意思嗎?
(C)
Powerful的意思是?


(3)
如果題目把only if 改成 if 要選(C)?
正解好像是 A

projection matrix與projection matrix之間的關係

(1)
請問projection matrix與 orthogonal projection matrix有什麼不同呢?

我的理解是:若一個projection matrix A，再加上A^t * A = A * A^t =I，則稱之 orthogonal projection matrix。
這理解正確嗎?

(2)
那orthogonal projection matrix A，必定A^t = A嗎?
(還是說projection matrix已經保證A^t=A了呢?)

(3)
我們知道，在歐式空間中的子空間W，且其基底為{v1,v2, ... vn}，A=[v1 v2 ... vn]
則B = A* (A^t * A)^-1 A^t。B為orthogonal projection matrix。

我想問的是，反向成立嗎? 即若B為orthogonal projection matrix，則B可用某矩陣A表示成 A*(A^t * A)^-1 * A^t

(a)x=0,y=1

(b)如何歸納呢?

S->0A,A->0B

那開頭一定是00xxx

可是沒有這個答案?

假設不存在>0的simple circuit，又E不空，

在G中找一條maximal path from A->…->D，A!=D

則in-degree(D)!=out-degree(D)，矛盾

請問這樣證明對嗎?

怎麼算?

d 樹問題

都只會解二元樹的題目，遇到這提就不會了，想了很久還是想不出來
希望有人能我解答一下

求解到這後，5X2=(-11)、2X2=11；X2的解如何求出?

線代題庫T5 P167














從倒數第四行推到<=，有什麼定理可以support嗎？


離散題庫T4 P80

解答是deg的平方和，似有考慮同個點出去又回來
但第一次模考問Qn長度為2的path數給的解答(Cn取2)*2ⁿ沒算重複點

所以以何為準？
老師課本給的path定義不是不含重複點嗎？

老師的答案是(B), tree是2 color上課有講..
但題目什麼都沒說, 看起來(C)(D)(E)好像可以選?
另份網路解答說, 因為only root的時候可以1 color, 所以通通都可以選.. 囧
請問是不是color問題只要選general case的minimum color就好了呢? 所以答案只有(B)? 謝謝

Q1:
這一題我查到的答案是7*6*5/7^3

我覺得奇怪她說有8個樓層 那為何1F不行呢= = 因為我自己一開始寫的答案是8*7*6/8^3

還是我題意沒有看清楚!!

semigroup

(N.*),where x*y = x^y for all x,y 屬於N

為什麼它不是半群呢@@

第二次模考

7(b)

(n*n Boolean matrices, +, *), where + is ∨ and * is ∧

is not a ring, why? 

11(b)

If a vector space is spanned by a set of n vectors, then every set of more than n vectors must be linearly dependent.

True

後面說"超過n個向量"的向量未必要屬於前面span的向量吧

那為何是對的

19(d) A is symmetric positive definite

e^-A is symmetric positive definite 

怎證？

離散數學

T or F
consider the 2^19 compositions of 20,the number of compositions in which each summand
even is 2^10

上課的時候沒有聽得很清楚
想請問一下那個2^19是怎麼來的
還有為什麼不是2^10而是2^9

線性代數及離散數學的勘誤表及考題資訊已更新

• 新增99線性代數各校試題配分表及99離散數學各校試題配分表


• 更新99線性代數試題詳解勘誤及99離散數學試題詳解勘誤

反矩陣延伸問題

U 為可逆，求 K 值?

解到這邊之後，不知道該如何往下求解？

請問下一步該怎麼求解？

關於idempotent matrix的rank性質

If A is a orthogonal projection matrix on B and B is subspace of R^m, rank(A)=trace(A).

True:
Because A is orthogonal projection matrix on B, eigenvalues of A are 0s and1s.
For all x in B, Ax=x. So the gm(1)=dim(B). For all y in B^perb =Ax=0. So the gm(0)=dim(B^per).
dim(B)+dim(B^per)=m =gm(1)+gm(0)=m  -> A is diagonalizable.

Because A is diagonalizable, trace(A)= gm(1)*1 + gm(0)*0=gm(1) = m - gm(0).
We know gm(0)=nullity(A),so trace(A)=gm(1)= m - nullity(A)=rank(A). In the conclusion, we get the rank(A) = trace(A).

請問上面證明，正確嗎?

還有如果一個矩陣P只是P^2=P (即idempotent matrix)
請問除了ker(P)與Im(P)呈直和，還有什麼性質嗎? 如eigenvalue , rank之類的。
而且應該沒法套用上面的論述吧?
即: If A is a idempotent matrix , rank(A)=trace(A). => False。

最後請問一個matrix P要被稱作orthogonal projection matrix，是不是要P^2=P, 且P^t=P呢?

謝謝~

線性代數

T OR F
A: 4*6
the number of general solution of ax=0 is at most 6

請問一下何謂AX=0 的general solution