123456789組成的3×3的矩陣的行列式最大的值是多少？

01-08

123456789怎樣運算等於1？ - abccsss 的回答
假定每個數字只能出現一次。

Mathematica代碼

較簡潔

Det/@N@Range@9~Permutations~{9}~ArrayReshape~{9!,3,3}//Max

較高效

Max@Table[Evaluate@Det@Quiet@Array[i[[3#+#2-3]],{3,3}],{i,Range@9~Permutations~{9}}]

$egin{Large} det egin{vmatrix} 9 2 4 \ 5 7 1 \ 3 6 8 \ end{vmatrix} = 412 end{Large}$

以上用Matlab暴力破解（枚舉 $9! = 362880$ 種情形），暫未輸出行列式相同的其他情形，貌似基本秒出。

max_det = 0; init_perm = reshape(1:9, [3, 3]); all_perms = perms(1:9);


for i = 1:size(all_perms, 1)

    matrix = all_perms(i, :);

    matrix = reshape(matrix, [3, 3]);

    det_value = det(matrix);
    if det_value &> max_det

        max_det = det_value;

        init_perm = matrix;

    end

end

對於三階的窮舉，可以不用det函數會比較簡單：

p = reshape(perms(1:9),"",3,3); M = max(sum(prod(p,2),3)-sum(prod(p,3),2));

並且如果用整數類型可以稍微快一些（sum和prod需要"native"參數）。不過上邊的方法有很多重複的情形。由於行列式交換行或列位置以及轉置都不會改變其絕對值大小，所以要計算的情況可以少很多。但是對於3階只算一次上邊的方法夠用了。

{Det[Partition[#~Join~{8,9},3]]/@Permutations@Range@7,Det[Partition[Insert[#,8,-4]~Append~9,3]]/@Permutations@Range@7}

極少的優化……

話題的語言還少個Mathematica,就我來吧

直接9!個結果存下來剛正面,0優化

Det[Partition[#, 3]] /@ Permutations[Range[9]] // Max

412

貼個毫無技術含量暴力程度max的python版。。。

import itertools import time


def max_matrix():

	begin = time.time()

	elements = [1, 2, 3, 4, 5, 6, 7, 8, 9]

	maxdet = 0

	maxmat = []

	for i in itertools.permutations(elements, 9):

		det = i[0] * i[4] * i[8] + i[1] * i[5] * i[6] + i[2] * i[3] * i[7] - i[2] * i[4] * i[6] - i[1] * i[3] * i[8] - i[0] * i[5] * i[7]

		if(det &> maxdet):

			maxdet = det

			maxmat = []

			for j in range(0, 9):

				maxmat.append(i[j])

	print "|" + str(maxmat[0]) + " " + str(maxmat[1]) + " " + str(maxmat[2]) + "|"

	print "|" + str(maxmat[3]) + " " + str(maxmat[4]) + " " + str(maxmat[5]) + "| = " + str(maxdet)

	print "|" + str(maxmat[6]) + " " + str(maxmat[7]) + " " + str(maxmat[8]) + "|"

	end = time.time()

	print str(end - begin) + "s used."

if __name__ == "__main__": max_matrix()

題目應該改成1 2 3 ...n^2組成n階行列式的最大值。並求最優解的時間複雜度才有意思。

C++版的暴力破解...最大值為412，總共36個解。

#include & #include & #include &


using namespace std;
inline int Determinant(const vector& v)

{

	return v[0]*v[4]*v[8] + v[2]*v[3]*v[7] + v[1]*v[5]*v[6] - v[2]*v[4]*v[6] - v[0]*v[5]*v[7] - v[1]*v[3]*v[8];

}
int main()

{

	vector& vec = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

int detValue = Determinant(vec); vector& mat; vector&&> result; while ( next_permutation(vec.begin(), vec.end()) ) { int value = Determinant(vec); if (detValue &< value) { detValue = value; mat.assign(vec.begin(), vec.end()); result.clear(); result.push_back(mat); } else if (detValue == value) { mat.assign(vec.begin(), vec.end()); result.push_back(mat); } } cout &<&< detValue &<&< endl; for (const auto item : result) { for (const auto i : item) cout &<&< i &<&< " "; cout &<&< endl; } return 0; }

把yellow的答案重排一下可得

9 4 2

3 8 6

5 1 7

很容易看出思路了。

1.所有數按大小在斜率為-1的對角線上依次排開。（即：987在一條對角線，654在一條，321在一條）很容易看出這是讓正向數值最大的方法。

2.對於反向的對角線，排除主對角線之外的任意兩個數之和相等，且乘積越大的，相應的主對角線元素越小。（也就是讓三個乘積的最大值最小，然後最大的結果再和最小的數相配這樣）

但是以上方法僅限於1~9的3x3矩陣，對於其它的矩陣不一定適用。

因為顯然這種方法要求正向和負向都只有對角線（或平行於對角線），但是4x4的行列式就開始有拐彎了。。。

然後，我感覺還有三個漏洞，一是貪心法不一定保證正向最大，也不一定保證反向最小，更不一定保證正反向之差最大。（不一定都是漏洞，可能有的是恆成立的）

但是我感覺對3x3的非負矩陣來說，貪心在多數情況下是可以拿到最大值的。

PS：試了很多組數，都是這個解，然後又試了一組[1 2 3 4 5 6 7 8 100]，顯然答案發生了變化，因為100的權值比8和7大太多，所以負向的時候直接就把2和1給了100。那麼這也就證明了貪心法確實有時候得不到最大值。

#python2

from itertools import permutations

from numpy import reshape

from numpy.linalg import det

print max(map(lambda m:det(reshape(m,(3,3))),permutations(xrange(1,10))))

結果：412

想問一下，有不用計算機的解法嗎？

C++：

#include & #include & using namespace std; int ans, a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int main() { do ans = max(ans, a[0] * (a[4] * a[8] - a[5] * a[7]) + a[1] * (a[5] * a[6] - a[3] * a[8]) + a[2] * (a[3] * a[7] - a[4] * a[6])); while (next_permutation(a, a + 9)); printf("%d ", ans); }

運行結果：

有更快的嗎？還有，你們寫那麼長幹嘛，就問我們最大的值，不要妄測需求。

412

[1, 4, 8]

[7, 2, 6]

[5, 9, 3]

[1, 5, 7]

[8, 3, 6]

[4, 9, 2]

[1, 7, 5]

[4, 2, 9]

[8, 6, 3]

[1, 8, 4]

[5, 3, 9]

[7, 6, 2]

[2, 4, 9]

[7, 1, 5]

[6, 8, 3]

[2, 6, 7]

[9, 3, 5]

[4, 8, 1]

[2, 7, 6]

[4, 1, 8]

[9, 5, 3]

[2, 9, 4]

[6, 3, 8]

[7, 5, 1]

[3, 5, 9]

[8, 1, 4]

[6, 7, 2]

[3, 6, 8]

[9, 2, 4]

[5, 7, 1]

[3, 8, 6]

[5, 1, 7]

[9, 4, 2]

[3, 9, 5]

[6, 2, 7]

[8, 4, 1]

[4, 1, 8]

[9, 5, 3]

[2, 7, 6]

[4, 2, 9]

[8, 6, 3]

[1, 7, 5]

[4, 8, 1]

[2, 6, 7]

[9, 3, 5]

[4, 9, 2]

[1, 5, 7]

[8, 3, 6]

[5, 1, 7]

[9, 4, 2]

[3, 8, 6]

[5, 3, 9]

[7, 6, 2]

[1, 8, 4]

[5, 7, 1]

[3, 6, 8]

[9, 2, 4]

[5, 9, 3]

[1, 4, 8]

[7, 2, 6]

[6, 2, 7]

[8, 4, 1]

[3, 9, 5]

[6, 3, 8]

[7, 5, 1]

[2, 9, 4]

[6, 7, 2]

[3, 5, 9]

[8, 1, 4]

[6, 8, 3]

[2, 4, 9]

[7, 1, 5]

[6, 8, 3]

[2, 4, 9]

[7, 2, 6]

[5, 9, 3]

[1, 4, 8]

[7, 5, 1]

[2, 9, 4]

[6, 3, 8]

[7, 6, 2]

[1, 8, 4]

[5, 3, 9]

[8, 1, 4]

[6, 7, 2]

[3, 5, 9]

[8, 3, 6]

[4, 9, 2]

[1, 5, 7]

[8, 4, 1]

[3, 9, 5]

[6, 2, 7]

[8, 6, 3]

[1, 7, 5]

[4, 2, 9]

[9, 2, 4]

[5, 7, 1]

[3, 6, 8]

[9, 3, 5]

[4, 8, 1]

[2, 6, 7]

[9, 4, 2]

[3, 8, 6]

[5, 1, 7]

[9, 5, 3]

[2, 7, 6]

[4, 1, 8]

計算機暴力窮舉；低端原始點的python代碼：

a=[1,2,3,4,5,6,7,8,9]


def det(a):

    i_1=a[0][0]*a[1][1]*a[2][2]

    i_2=a[0][1]*a[1][2]*a[2][0]

    i_3=a[0][2]*a[1][0]*a[2][1]

    i_4=a[0][2]*a[1][1]*a[2][0]

    i_5=a[0][1]*a[1][0]*a[2][2]

    i_6=a[0][0]*a[1][2]*a[2][1]
    f=i_1+i_2+i_3-i_4-i_5-i_6
    return f
b=a[:]

n=0
for i_1 in b:

    b_1=b[:]

    b_1.remove(i_1)

    for i_2 in b_1:

        b_2=b_1[:]

        b_2.remove(i_2)

        for i_3 in b_2:

            b_3=b_2[:]

            b_3.remove(i_3)

            for i_4 in b_3:

                b_4=b_3[:]

                b_4.remove(i_4)

                for i_5 in b_4:

                    b_5=b_4[:]

                    b_5.remove(i_5)

                    for i_6 in b_5:

                        b_6=b_5[:]

                        b_6.remove(i_6)

                        for i_7 in b_6:

                            b_7=b_6[:]

                            b_7.remove(i_7)

                            for i_8 in b_7:

                                b_8=b_7[:]

                                b_8.remove(i_8)

                                for i_9 in b_8:

                                    c=[[i_1,i_2,i_3],[i_4,i_5,i_6],[i_7,i_8,i_9]]

                                    if det(c) &> n:

                                        n = det(c)
print(n)

for i_1 in b: b_1=b[:] b_1.remove(i_1) for i_2 in b_1: b_2=b_1[:] b_2.remove(i_2) for i_3 in b_2: b_3=b_2[:] b_3.remove(i_3) for i_4 in b_3: b_4=b_3[:] b_4.remove(i_4) for i_5 in b_4: b_5=b_4[:] b_5.remove(i_5) for i_6 in b_5: b_6=b_5[:] b_6.remove(i_6) for i_7 in b_6: b_7=b_6[:] b_7.remove(i_7) for i_8 in b_7: b_8=b_7[:] b_8.remove(i_8) for i_9 in b_8: c=[[i_1,i_2,i_3],[i_4,i_5,i_6],[i_7,i_8,i_9]] if det(c) == n: print(c[0]) print(c[1]) print(c[2]) print()

import itertools import numpy as np

maxDet = max( map( np.linalg.det, map( lambda x:np.array(x).reshape(3,3), itertools.permutations(range(1,10),9) ) ) ) print(maxDet)

沒有matlab快，這是為什麼？

東施效顰一下 @鄒沖

#include& #include& #include& #include& #include& using namespace std; int main() {

int temp; int target = INT_MIN; int target_marix[9]; int numbers[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; while (next_permutation(numbers, numbers + 9)) { temp = numbers[0] * numbers[4] * numbers[8] + numbers[3] * numbers[7] * numbers[2] + numbers[1] * numbers[5] * numbers[6]- (numbers[2] * numbers[4] * numbers[6] + numbers[1] * numbers[3] * numbers[8] + numbers[5] * numbers[7] * numbers[0]); if (target &< temp) { target = temp; for (int i = 0; i &< 9; i++) { target_marix[i] = numbers[i]; } } } for (int i = 0; i &< 9; i++) { cout &<&< target_marix[i] &<&< " "; if ((i + 1) % 3 == 0) cout &<&< endl; } }

前面已經有了python，c和MMA的代碼了，我來一發matlab的吧

p=perms(1:9); [n,~]=size(p); z=zeros(n,1); for i=1:n z(i)=det(reshape(p(i,:),3,3)); end max(z) id=find(z==max(z)); for i=1:length(id) disp(reshape(p(id(i),:),3,3)); end

結果最大值是412，最大值點如下：

9 2 4

5 7 1

3 6 8

9 3 5

4 8 1

2 6 7

9 4 2

3 8 6

5 1 7

9 5 3

2 7 6

4 1 8

8 1 4

6 7 2

3 5 9

8 3 6

4 9 2

1 5 7

8 4 1

3 9 5

6 2 7

8 6 3

1 7 5

4 2 9

7 1 5

6 8 3

2 4 9

7 2 6

5 9 3

1 4 8

7 5 1

2 9 4

6 3 8

6 2 7

8 4 1

3 9 5

6 3 8

7 5 1

2 9 4

6 7 2

3 5 9

8 1 4

6 8 3

2 4 9

7 1 5

5 1 7

9 4 2

3 8 6

5 7 1

3 6 8

9 2 4

5 9 3

1 4 8

7 2 6

4 2 9

8 6 3

1 7 5

4 1 8

9 5 3

2 7 6

4 8 1

2 6 7

9 3 5

4 9 2

1 5 7

8 3 6

3 5 9

8 1 4

6 7 2

3 9 5

6 2 7

8 4 1

3 8 6

5 1 7

9 4 2

3 6 8

9 2 4

5 7 1

2 4 9

7 1 5

6 8 3

2 9 4

6 3 8

7 5 1

2 7 6

4 1 8

9 5 3

2 6 7

9 3 5

4 8 1

1 5 7

8 3 6

4 9 2

1 4 8

7 2 6

5 9 3

1 7 5

4 2 9

8 6 3

一共是33個。少的那三個估計來自於MATLAB的計算誤差，懶得改了。