LP的線性獨立測試

Question

我們有一組向量P1，...，Pk。每個矢量都有n維。如果下面問題的唯一解決方案是λ（i）= 0，那麼這些向量是線性無關的：對於每個0，λ（1）P1 +λ（2）P2 + ... + λ（k）Pk = 0;

其中lambda（i）是一個實數。 更嚴格的配方可在https://en.wikipedia.org/wiki/Linear_independence

我正在處理與長達一段時間的LP建模這個問題，迄今爲止沒有答案。你能幫我解決這個問題嗎？ 謝謝。

Answer 1

假設您正在處理尺寸爲n的矢量空間。如果有更多的向量P1,...,Pk，則輸入不是線性獨立的;所以假設k<=n。目標是確定輸入的線性外殼的尺寸。解決在{1,...,n}形式

max e_{i}x s. t. Ax = e_{i} 

每個i其中e_{i}表示i個單位矢量的n線性節目。可解線性程序的數量應該產生輸入的線性外殼的尺寸，這意味着當且僅當輸入線性獨立時，這些數字等於k。