2010-01-31

complete graph Kn

Give a complete graph Kn of n distinct vertices, (a)determine the number of complete subgraphs Kn-1(of n-1 vertices) that the complete graph Kn contains.

(b)determine the number of complete subgraphs Km(of m vertices) that the complete graph Kn contains.(m<=n)
請問一下這兩題答案是

(a) 我的想法:
Kn 每扣掉一個點 就會有一個Kn-1 所以 會有 n 個Kn-1
(b)
我的法想 最少m=1
1<=Km<=n

不知道我這樣對不對
希望高手能夠指導我一下

2010-01-30

[離散]圖論

G:planar graph => G中存在一點degree<=5


P.f :請問這題證到後來e>=3V然後矛盾就得證了,是為什麼??

[離散]D_n的遞迴式

請問亂序的遞迴式D_n的推導要怎樣討論比較好理解記憶呢 ?

如果觀察1來看

1放在i!=1的位置 則有n-1個選擇

剩下的n-1個數再做亂序為D_n-1(這個好像是i不能放1在的情形)

再考慮1放在i 且i放在1的情形 則剩下的n-2個數亂序為D_n-2

全部情形為 Dn=(n-1)(D_n-1 + D_n-2)

去討論i放不放1的情形 感覺不是那麼直觀耶...

請問有比較好理解的方式嗎 ?

因為有時候沒想清楚 會直接寫成D_n = (n-1)D_n-1

幾個問題





18題的 D選項是 sigma n,

E是 sigma (1/ 與n互質的數 ).....(打不出來@@ )


這兩題 麻煩解答了 謝謝

2010-01-28

遞迴

遞迴式子我想應該是這樣列
a_n=a_n-1+a_n-3,n>=4
a1=1,a2=1,a3=2

可是 alpha不知道要怎樣解.....


麻煩解答了 謝謝

2010-01-27

dual

The principle of duality holds for Boolean and rings
true or false?

麻煩解答了 謝謝

2010-01-26

93交大數學


 想跟大家討論一下這五題是非題..
我寫的答案是?TTTT,
不過不太確定..尤其是1跟2,麻煩指導了~。

2010-01-24

"四大空間的orthogonal basis"之回應



恩 之前看到下面回文想要回答
可是把矩陣用網頁語法實在是太不方便了
用illustrator也挺麻煩的
乾脆用照片解釋
希望能幫忙解決SVD的問題

交大數學



想請問一下這兩題,
不知道第一題遞迴這樣列對嗎?
T(n) = 1.05T(n-1)
T(0) = 50000
不太會列..= =

而第二題,求出E=120後,不知道還有什麼資訊可以利用
麻煩題點一下~感謝。

對了,不知道大家已經做幾份考古題了,
雖然有朋友一起念,不過他們進度似乎有點落後XD
不知道有沒有人願意交換一下答案討論一下的~thx

[線代] 三題證明請益

http://twpic.org/uploads2/c916573d7d.jpg

麻煩各位了~謝謝 !!!

[離散] 生成函數

Find the generating function for the number of integer solution to x1+x2+x3+x4=r with1<=x1<=x2<=x3<=x4.

------------------
請問可以用 y1=x1-1 y2=x2-x1 y3=x3-x2 y4=x4-x3
x1=y1+1
x2=y1+y2+1
x3=y1+y2+y3+1
x4=Y1+y2+y3+y4+1

then
x1+x2+x3+x4=4y1+3y2+2y3+y4+4=r,y1~y4>=0這樣求算嗎 ?

排列組合

We are given a red box,a blue box,and a green box.We also have 10 red balls,10 blueballs,and 10 green balls.Balls of the same color are considered identical.
Consider the following constraints:
(1) No box contains a ball that has the same color as the box
(2) No box is empty

請問這題怎麼解比較好呢?


謝謝

2010-01-23

CRT

請問這題要如何拆解才能解CRT?
X=7 mod 9
X=4 mod 12
X=16 mod 21
n1,n2,n3需要互質 這題該如何拆解呢?


麻煩解答了 感謝

[線代] 一題題目請益

http://twpic.org/uploads2/175d66d767.jpg

請問上面這題有辦法用老師課本3版P5-66的方法做嗎?!!!

還是只能用P5-23的方法直接作呢?!! 謝謝 !

2010-01-22

數學

How many different dice are there? Two dice are considerd identical if they become exactly the same after proper rotations and flips.

請問這題的意思是要證排列組合還是波里雅(後段感覺很波李雅..),請問該怎麼證明?







另外還想請問這一題該怎麼做?

四大空間的orthogonal basis

(a) Find the SVD of A =
┌3 2 2┐
└2 3 -2┘
(b) Use (a) to find an orthogonal basis for each of the four subspaces
R(A), C(A), N(A), and N(A^T)

請問要怎麼使用SVD 去找 四大空間的orthogonal basis
完全沒有頭緒

直和


請問這題是不是每個Ui都是?


感謝回答

線性代數習題7-9(T or F)

Let T be a linear operator on V. If||T(x)||=||x||,then T is onto.

本題的上一題是問one-to-one 很好證(即證Ker(T)={0})

那為什麼one-to-one 加上||T(x)||=||x|| 就可得T為 onto 呢

Cyclic group

Let G=< a > with 0(a)=n

prove that a^k, k屬於正整數, generates G iff k and n are relatively prime.

請問這要如何證明

謝謝

2010-01-21

[線代] Eigenspace請益

http://twpic.org/uploads2/136313f9f1.jpg

請教一下~
這題最後求出來的eigenspace有錯嗎?!!!謝謝!!!!

2010-01-20

交大數學














第三題意思很簡單..但是遞迴好難列= =
其他兩題則是不知道該怎麼下手較好..
麻煩助較大致解釋一下了~感謝

reducible?

f(x)=x^3+x+1 is reducible in R[x] and C[x]

reducible的意思是可以把這個方程式拆成3項1次式的乘積嗎?
也就是 f(x)=a(x-b)(x-c)(x-d)?
a,b,c,d屬於R or C (若是佈於C)

另外
let A=(0,1). a sequence is represented by Xn=1-1/n,
then the sequence converges to A
數列最後會收斂到 1,而 A的範圍沒包括1所以是 False?

麻煩解答了 謝謝

[離散] Ordering and ...?

2. 我的想法: 對15作整數分割
所有數字可以由{1,2,4,8}組合
那就可以加速之後的服務速度
不太清楚題目要的是不是如此..

3. (a) 我的想法: 字典排序法下最少的比較次數相當於第一次比較即結束, 所以b只要為 {4XXXXX, 5XXXXXX, 6XXXXX} 即可?
(b) 我的想法: 因為b>a, 所以只要c贏過b即可, 又c與b第一個分數相同, 所以只要c的第二字比b即可?
(c) 我的想法: 不知道如何下手..




請問上面兩題如何解答、是否如此解? 謝謝

2010-01-19

[線代] - 台大95














這題除了一個一個TRY,有更快的方法知道答案嗎?

因為配分才三分,這張考卷又30題左右~~

可以猜or拆出答案嗎?

謝謝

2010-01-17

正(半)定矩陣判斷

A為3*3矩陣,A為正(半)定
書上定理說 A的所有主子矩陣其行列式>(=)0
但在課本P8-88 注意事項8-21提到
這個矩陣
[10 0]
[00 0]
[00-1] 去掉第二列第二行,其行列式<0,所以不是正半定>=0,這樣不是跟定理有矛盾嗎?


另外,請問這題複雜度該怎麼求呢?
2^((2logn)^1/2)


麻煩解答了 謝謝

Householder

[1 -1]
[-1 1] = A, be the 3*2 matrix.
[1 -1]
Find a matrix H such that HA = R is an upper triangular matrix.

這題由題目可以知道求Householder,也知道可以令 x = [1 -1 1]^T,最後答案求出來是
[√3 -√3]
[  0     0]
[  0     0]
但想請問的是:如果題目給的矩陣不像此題恰好只差一個負號,那請問 x 要怎麼令呢?不知道我的問題表達夠不夠清楚..Orz

另外,假設題目給說T(x)=A(x),求對L之reflect,
L spanned by [4 3]^T,想請問法向量該怎麼令= =?

感謝!

2010-01-16

集合論

A,B,C為3個set
(A-B)⊕(A-C)=空集合
滿足此條件A,B,C之間的關係是什麼?


麻煩解答了 感謝

2010-01-14

圖論

請問這題該如何解呢 ?



what are the directed graph in which each vertex has at most one outgoing edge?
還有這題要回答什麼呢?

麻煩解答 謝謝

2010-01-13

[離散] 圖論部分

Show how to label a path of N vertices with the integers 1,2,.......,N such that

the absolute values of the difference of the labels of adjacent vertices are all different.

You can construct it inductively.



請問一下題目意思,以及該如何解答?


謝謝

[離散] - 94交大









這題我用想的,覺得(1)(2)是獨立的,答案卻是1.2.3
這題可以用想的嗎~?

還是一定得要用機率算?(機率都忘光光了)

2010-01-12

Polya

請問如何用polya解正方體(對面著色,可著六色,考慮翻轉何旋轉)?

另外,
Given the vectors α=[2,3,0]、β=[0,-3,-2],γ=[0,1,1]. Find the orthogonal projection of α+β along γ.
請問這題的意思是 把[2,0,-2]正交投影在 [0,1,1]上嗎?

麻煩解答了 謝謝

2010-01-11

[線代]-94台大










請問一下這題答案多少? & 怎麼想?

請問正(半)定和正規矩陣的關係

我看老師書上的定義
over C 時 quadratic form 是實係數的矩陣 必為 Hermitian 而 Hermitian就是正規矩陣
over C 時 的正定矩陣的 quadratic form必為實係數 所以為 Hermitian
所以over C 時的正定矩陣必為正規矩陣
over R 時 正定矩陣不一定要Symmetric(Hermitian)
所以只有Symmetric的正定矩陣是正規矩陣是嗎 ?(重點在於它Symmetric)

還是有什麼詳細一點的說法來判定正(半)定 和正規矩陣之間的關係呢 ?
(當然T*T=TT*是最基本的定義 請問有什麼適用在不為Hermitian的正定矩陣的判斷法嗎 ?)

2010-01-10

Cayley-Hamilton

請問一下這一題,有點麻煩的算式..不過想問一下求解一定都要拆開嗎?
直接展開再除不是也可以。






求出Pa(x)後除以題目,得到商式: -1-3-5-5-1+8+16+16,餘式:-1+5-4(ie.-A^2+5A-4)
求出來的答案是↓
[47 0 0]
[0 48 -50]
[0 50 48]

但老師給的答案是↓
[7 0 0]
[0 8 -10]
[0 10 8]

麻煩了..感謝

幾個問題













1.不大懂題目的意思P1,P2是向量,向量連成的線段是??這題感覺像是高中的題目......

b跟c題也不會

4.題目裡只說(G,*)是群,如果沒定義*的運算,這題可以確定答案嗎?
另外還有一題,求其bigO
k=0
for (i=0 to n-1)
for (j=0 to i^2 -1)
if (j%i==0)
for(z=0 to j-1)
k++;
這題該怎麼解?
問題有點多 麻煩解答了 謝謝

2010-01-08

內積問題


這題題目似乎有錯
會<0
假設題目沒錯要如何求第二小題呢?
麻煩解答了 謝謝

Cayley-Hamilton

0 0 -2
0 1 0 , find e^At
1 0 3


像這種 如果想要用 Cayley-Hamilton + 極小多項式做

特徵方程式 : (X-1)^2 * (X-2)
極小多項式 : (X-1) * (X-2)

令 f(x) = e^xt

因為 極小多項式 可整除 f(x)

所以f(x) = a(X-1) + b

X=1 e^t = b
X=2 e^2t - e^t = a

再帶回 a(A-1I) + bI
這樣對嗎?

另外 我想問的是 如果今天 極小多項式 : (X-1)^2 * (X-2)

那我則要令f(x)= a(X-1) (X-2) + b(X-1) + c
可是 X 只能帶1 和 2
要如何求出 第三個變數?

2010-01-07

圖論


上課筆記的note寫說
Km,n 的spanning tree 有 m^(n-1)*n^(m-1)種
請問如何求的呢?


感謝解答

2010-01-06

線性代數

一、
A=[2 -3 -6 -4]
     [1 5 -3 11]
Consider A, find a particular solution and all the homegeneous solution to Ax=[2 1]^T(直的不好打).想請問這時候的X應該怎麼取比較好求?

二、向量 A=x+y+z 和向量 B=y-z 構成之平面法向量與向量 C=x-2z之夾角為何?
(題目真的是中文..XD)  正常不是會給向量的定義嗎..這樣可以求嗎?




想請問(B)小題應該怎麼解?
另外還想請問,老師的書上有另外多問了一個問題,他是插在(a)小題前面的,題目如下:
Show that there exists a matrix, call C in R^(p*m) with rank(C)=p such that CA=I.

應該是要我們求左反矩陣嘛,可是寫到rank(A)=p,dim(RS(A))=......再來就沒下文了XDD

問題有點多,麻煩了..

2010-01-04

[線代] 一題Markov題型請益

http://twpic.org/uploads2/f9dd735880.jpg

上面這題麻煩各位幫忙解惑一下~謝謝 !!

遞迴求解

T(n)=2T(n/2)+logn // 原式

=4T(n/4)+3logn-2
=8T(n/8)+7logn-10
= ...
=2^kT(n/2^k)+(2^k-1)logn-XXX
_________________________^^^ 求不出closed form....

麻煩解答了,感謝。

2010-01-03

[線代] 矩陣空間

題目是 是非
R^2*2 has a basis consisting of matrices whose trace is zero.
答案是False
我想問一下
這邊題目是說一組基底可以組成一個矩陣是什麼意思
是說一組基底取

還是該怎麼想?