Chủ đề này có 13 trả lời

[bocvacdem]

Các anh chị cho em xin cách chứng minh 2 bài toán này với ạ. 

1. Cho ma trận $A = (a_{ij})_{4x4}$ với $a_{ij} \in \{-1,1\}$. CMR $ | \det (A) | \leq 16$
2. Cho ma trận $A = (a_{ij})_{5x5}$ với $a_{ij} \in \{-1,1\}$. CMR $ | \det (A) | \leq 64$

Bài viết đã được chỉnh sửa nội dung bởi bocvacdem: 16-01-2024 - 01:19

[nmlinh16]

Đây là hệ quả của một kết quả tổng quát hơn, gọi là bất đẳng thức Hadamard.

Nói ngắn gọn thì nếu ma trận vuông $A$ có các cột $v_1,\ldots,v_n \in \mathbb{R}^n$ thì $\det(A)$ là thể tích (có dấu) của hình hộp $n$-chiều dựng trên các vectơ $v_1,\ldots,v_n$, nên $|\det(A)|$ không vượt quá tích độ dài của chúng (đẳng thức xảy ra khi các vectơ này đôi một trực giao, hay hình hộp mà chúng dựng lên là hình hộp chữ nhật). Bất đẳng thức này có thể được chứng minh bằng phép trực giao hóa Gram-Schmidt (nói nôm na là từ đỉnh của vectơ $v_1$, ta kẻ vuông góc xuống siêu phẳng ($(n-1)$-chiều) xác định bởi các vectơ $v_2,\ldots,v_n$, rồi cứ tiếp tục như vậy.

 

Trong bài toán trên, các cột của $A$ đều là các vectơ có độ dài $\sqrt{n}$, nên $|\det(A)| \le (\sqrt{n})^n = n^{n/2}$. Lần lượt thay $n=4$ và $n=5$, ta có các bất đẳng thức cần chứng minh.

[bocvacdem]

Đây là hệ quả của một kết quả tổng quát hơn, gọi là bất đẳng thức Hadamard.

Nói ngắn gọn thì nếu ma trận vuông $A$ có các cột $v_1,\ldots,v_n \in \mathbb{R}^n$ thì $\det(A)$ là thể tích (có dấu) của hình hộp $n$-chiều dựng trên các vectơ $v_1,\ldots,v_n$, nên $|\det(A)|$ không vượt quá tích độ dài của chúng (đẳng thức xảy ra khi các vectơ này đôi một trực giao, hay hình hộp mà chúng dựng lên là hình hộp chữ nhật). Bất đẳng thức này có thể được chứng minh bằng phép trực giao hóa Gram-Schmidt (nói nôm na là từ đỉnh của vectơ $v_1$, ta kẻ vuông góc xuống siêu phẳng ($(n-1)$-chiều) xác định bởi các vectơ $v_2,\ldots,v_n$, rồi cứ tiếp tục như vậy.

 

Trong bài toán trên, các cột của $A$ đều là các vectơ có độ dài $\sqrt{n}$, nên $|\det(A)| \le (\sqrt{n})^n = n^{n/2}$. Lần lượt thay $n=4$ và $n=5$, ta có các bất đẳng thức cần chứng minh.

Dạ vâng, em cảm ơn anh. Em có tìm ra bài này là ma trận Hadamard. Để em suy nghĩ thêm về cách giải này ạ. 

[bocvacdem]

Em xin gửi một đoạn cách giải của em cho bài 1 ạ. Phần sau chứng minh, em có sử dụng code để tìm ra ma trận thỏa mãn. Nếu anh chị nào có ý tưởng chứng minh phần này thì cho em xin gợi ý ạ.

Xuất phát từ bài toán, cho $A = (a_{ij})_{nxn}$ với $a_{ij} \in \{-1;1\}$. Ta chứng minh được $\det(A) \vdots 2^{n-1}$. Bên cạnh đó, đối với $n=3$, $-6 \leq \det A \leq 6$, suy ra $min(\det A) = -4$, $max(\det A) = 4$.
Quay lại bài toán, khai triển Laplace tại dòng 1, ta có: $$|\det A | = |a_{11} A^{*}_{11} + a_{12} A^{*}_{12} + a_{13} A^{*}_{13} + a_{14} A^{*}_{14}| \leq |a_{11} A^{*}_{11}| + |a_{12} A^{*}_{12}| + |a_{13} A^{*}_{13}| + |a_{14} A^{*}_{14}| = 16$$

Một trong các trận thỏa mãn $\det = 16$ và $\det = -16$ là

$A = \begin{bmatrix} 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ -1 & 1 & 1 & -1 \\ 1 & 1 & 1 & 1 \\ \end{bmatrix} , B = \begin{bmatrix} -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & -1 \\ -1 & 1 & 1 & -1 \\ 1 & 1 & 1 & 1 \\ \end{bmatrix}$

Bài viết đã được chỉnh sửa nội dung bởi bocvacdem: 16-01-2024 - 04:03

[nmlinh16]

Em xin gửi một đoạn cách giải của em cho bài 1 ạ. Phần sau chứng minh, em có sử dụng code để tìm ra ma trận thỏa mãn. Nếu anh chị nào có ý tưởng chứng minh phần này thì cho em xin gợi ý ạ. 

Xuất phát từ bài toán, cho $A = (a_{ij})_{nxn}$ với $a_{ij} \in \{-1;1\}$. Ta chứng minh được $\det(A) \vdots 2^{n-1}$. Từ đó, đối với $n=3$, $|\det A| \leq 4$. 
Quay lại bài toán, khai triển Laplace tại dòng 1, ta có: $$|\det A | = |a_{11} A^{*}_{11} + a_{12} A^{*}_{12} + a_{13} A^{*}_{13} + a_{14} A^{*}_{14}|  \leq |a_{11} A^{*}_{11}| + |a_{12} A^{*}_{12}| + |a_{13} A^{*}_{13}| + |a_{14} A^{*}_{14}| = 16$$

 

Một trong các trận thỏa mãn $\det = 16$ và  $\det = -16$ là

 

$A = \begin{bmatrix} 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ -1 & 1 & 1 & -1 \\ 1 & 1 & 1 & 1 \\ \end{bmatrix} , B = \begin{bmatrix} -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & -1 \\ -1 & 1 & 1 & -1 \\ 1 & 1 & 1 & 1 \\ \end{bmatrix}$

 

$\det(A)$ chia hết cho $2^{n-1}$ thì $\det(A) = 0$ hoặc $|det(A)| \ge 2^{n-1}$. Bạn kết luận "$\le$" là bị ngược.

[bocvacdem]

$\det(A)$ chia hết cho $2^{n-1}$ thì $\det(A) = 0$ hoặc $|det(A)| \ge 2^{n-1}$. Bạn kết luận "$\le$" là bị ngược.

Em sửa lại thành như vậy đã hợp lý chưa ạ

[nmlinh16]

Bạn không thể dùng tính chia hết cho $4$ để kết luận $|\det(A)| \le 4$ được, nếu $\det(A) = 8$ thì sao?

[Konstante]

Đặt $A = \left(v_1,\dots,v_n\right)$ với $v_i$ là các vector cột của $A$, nếu các $v_i$ là phụ thuộc tuyến tính thì $\det A = 0$ và bất đẳng thức là hiển nhiên, do vậy ta chỉ cần xét trường hợp các $v_i$ tạo nên một cơ sở.

 

Sử dụng thủ tục trực giao hóa Gram-Schmid cho $\left\{v_1,\dots, v_n\right\}$, ta thu được $$A = PB$$ trong đó $P$ là ma trận trên với các phần tử trên đường chéo chính bằng $1$, còn $B = \left(e_1,\dots,e_n\right)$ trong đó các vector $e_i$ thỏa mãn quan hệ truy hồi

• $e_1 = v_1$,
• $e_i$ là hình chiếu của $v_i$ lên mặt phẳng $\texttt{vect} \left(e_1,\dots,e_{i-1}\right)$

Do $P$ là ma trận trên với đường chéo chính là $1$ nên $\det P = 1$. Hơn nữa $\left\{e_1,\dots,e_n \right\}$ là một cơ sở trực giao (nhưng không phải trực chuẩn), nên $$\lvert \det B \rvert = \lVert e_1 \rVert \dots \lVert e_n \rVert $$và do $e_i$ là hình chiếu của $v_i$ nên $\lVert e_i \rVert \leq \lVert v_i \rVert$, kéo theo $$\lvert \det B \rvert \leq \lVert v_1 \rVert \dots \lVert v_n \rVert$$Ta đã biết $A = PB$ nên $\det A = \det P \det B$, do vậy $$\lvert \det A \rvert \leq \lVert v_1 \rVert \dots \lVert v_n \rVert$$

Bài viết đã được chỉnh sửa nội dung bởi Konstante: 16-01-2024 - 03:50

[bocvacdem]

Bạn không thể dùng tính chia hết cho $4$ để kết luận $|\det(A)| \le 4$ được, nếu $\det(A) = 8$ thì sao?

À dạ, do em nói sai. Vì $-6 \leq \det A \leq 6$, kết hợp chia hết cho 4 mới được vậy ạ

[nmlinh16]

À dạ, do em nói sai. Vì $-6 \leq \det A \leq 6$, kết hợp chia hết cho 4 mới được vậy ạ

ok, vậy thì được

[bocvacdem]

Đặt $A = \left(v_1,\dots,v_n\right)$ với $v_i$ là các vector cột của $A$, nếu các $v_i$ là phụ thuộc tuyến tính thì $\det A = 0$ và bất đẳng thức là hiển nhiên, do vậy ta chỉ cần xét trường hợp các $v_i$ tạo nên một cơ sở.

 

Sử dụng thủ tục trực giao hóa Gram-Schmid cho $\left\{v_1,\dots, v_n\right\}$, ta thu được $$A = PB$$ trong đó $P$ là ma trận trên với các phần tử trên đường chéo chính bằng $1$, còn $B = \left(e_1,\dots,e_n\right)$ trong đó các vector $e_i$ thỏa mãn quan hệ truy hồi

• $e_1 = v_1$,
• $e_i$ là hình chiếu của $v_i$ lên mặt phẳng $\texttt{vect} \left(e_1,\dots,e_{i-1}\right)$

Do $P$ là ma trận trên với đường chéo chính là $1$ nên $\det P = 1$. Hơn nữa $\left\{e_1,\dots,e_n \right\}$ là một cơ sở trực giao (nhưng không phải trực chuẩn), nên $$\lvert \det B \rvert = \lVert e_1 \rVert \dots \lVert e_n \rVert $$và do $e_i$ là hình chiếu của $v_i$ nên $\lVert e_i \rVert \leq \lVert v_i \rVert$, kéo theo $$\lvert \det B \rvert \leq \lVert v_1 \rVert \dots \lVert v_n \rVert$$Ta đã biết $A = PB$ nên $\det A = \det P \det B$, do vậy $$\lvert \det A \rvert \leq \lVert v_1 \rVert \dots \lVert v_n \rVert$$

Anh cho em hỏi tại sao lại có được $A = PB$ với $P$ là ma trận trên, có các phần tử trên đường chéo chính bằng 1 vậy ạ. 
Em thử lấy ví dụ $v = \{v_1 = (1,-1,0), v_2 = (2,0,-2), v_3 = (3,-3,3) \}$, hệ véc tơ này là ĐLTT. Khi đó ta có được $e_1 = v_1 = (1,-1,0), e_2 = v_2 - \frac {u_1^T v_2}{u_1^T u_1} u_1 = (1, 1, -2), e_3 = v_3 - \frac {u_1^T v_3}{u_1^T u_1} u_1 - \frac {u_2^T v_3}{u_2^T u_2} u_2 = (1, 1,1)$

$P = AB^{-1}$ không có các phần tử trên đường chéo chính bằng 1. Không biết em có bị sai ở đoạn nào không vậy anh. 

Bài viết đã được chỉnh sửa nội dung bởi bocvacdem: 16-01-2024 - 18:01

[Konstante]

Chết thật, mình viết nhầm, phải là $A = BP$ (nhưng không ảnh hưởng đến lời giải). Để hiểu tại sao $P$ là ma trận trên với đường chéo chính là $1$, ta tính toán một ví dụ khi $n = 3$. Theo thủ tục Gram-Schmid $$\begin{align*}e_1 &= v_1 \\ e_2&= v_2 - \frac{\langle v_2,e_1\rangle}{\lVert e_1\rVert^2} e_1 \\ e_3 &= v_3 - \frac{\langle v_3, e_1\rangle}{\lVert e_1 \rVert^2} e_1 - \frac{\langle v_3, e_2\rangle}{\lVert e_2 \rVert^2}  e_2\end{align*}$$Hay là $$\begin{align*}v_1 &= e_1 \\ v_2 &= \frac{\langle v_2,e_1\rangle}{\lVert e_1\rVert^2} e_1+e_2 \\ v_3 &= \frac{\langle v_3, e_1\rangle}{\lVert e_1 \rVert^2} e_1 + \frac{\langle v_3, e_2\rangle}{\lVert e_2 \rVert^2}  e_2 + e_3\end{align*}$$Viết dưới dạng ma trận$$\begin{pmatrix} v_1 & v_2 & v_3 \end{pmatrix} = \begin{pmatrix} e_1 & e_2 & e_3 \end{pmatrix} \begin{pmatrix} 1 & \frac{\langle v_2,e_1\rangle}{\lVert e_1\rVert^2} & \frac{\langle v_3,e_1\rangle}{\lVert e_1\rVert^2} \\ 0 & 1 & \frac{\langle v_3,e_2\rangle}{\lVert e_2\rVert^2} \\ 0 & 0 & 1\end{pmatrix}$$Với trường hợp cụ thể $$v_1 = \begin{pmatrix}1 \\ -1 \\ 0\end{pmatrix},v_2 =  \begin{pmatrix}2 \\ 0 \\ -2\end{pmatrix}, v_3 =  \begin{pmatrix}3 \\ -3 \\ 3\end{pmatrix}$$ta tính được $$e_1 = \begin{pmatrix}1 \\ -1 \\ 0\end{pmatrix}, e_2 = \begin{pmatrix}1 \\ 1 \\ -2\end{pmatrix},e_3 = \begin{pmatrix}1 \\ 1 \\ 1\end{pmatrix}$$ và $$\langle v_2, e_1\rangle = 2, \langle v_3, e_1 \rangle = 6,\langle v_3,e_2\rangle = -6, \lVert e_1 \rVert^2 = 2,\lVert e_2 \rVert^2 = 6$$Dễ dàng kiểm tra lại$$\begin{pmatrix}1 & 2 & 3 \\ -1 & 0 & -3 \\ 0 & -2 & 3\end{pmatrix} = \begin{pmatrix}1&1&1 \\-1&1&1 \\ 0&-2&1\end{pmatrix}\begin{pmatrix}1&1&3\\0&1&-1\\0&0&1\end{pmatrix}$$

Bài viết đã được chỉnh sửa nội dung bởi Konstante: 16-01-2024 - 22:40

[bocvacdem]

Đặt $A = \left(v_1,\dots,v_n\right)$ với $v_i$ là các vector cột của $A$, nếu các $v_i$ là phụ thuộc tuyến tính thì $\det A = 0$ và bất đẳng thức là hiển nhiên, do vậy ta chỉ cần xét trường hợp các $v_i$ tạo nên một cơ sở.
 
Sử dụng thủ tục trực giao hóa Gram-Schmid cho $\left\{v_1,\dots, v_n\right\}$, ta thu được $$A = PB$$ trong đó $P$ là ma trận trên với các phần tử trên đường chéo chính bằng $1$, còn $B = \left(e_1,\dots,e_n\right)$ trong đó các vector $e_i$ thỏa mãn quan hệ truy hồi

• $e_1 = v_1$,
• $e_i$ là hình chiếu của $v_i$ lên mặt phẳng $\texttt{vect} \left(e_1,\dots,e_{i-1}\right)$

Do $P$ là ma trận trên với đường chéo chính là $1$ nên $\det P = 1$. Hơn nữa $\left\{e_1,\dots,e_n \right\}$ là một cơ sở trực giao (nhưng không phải trực chuẩn), nên $$\lvert \det B \rvert = \lVert e_1 \rVert \dots \lVert e_n \rVert $$và do $e_i$ là hình chiếu của $v_i$ nên $\lVert e_i \rVert \leq \lVert v_i \rVert$, kéo theo $$\lvert \det B \rvert \leq \lVert v_1 \rVert \dots \lVert v_n \rVert$$Ta đã biết $A = PB$ nên $\det A = \det P \det B$, do vậy $$\lvert \det A \rvert \leq \lVert v_1 \rVert \dots \lVert v_n \rVert$$

Dạ vâng em cảm ơn anh. Tiện thể anh cho em hỏi tại sao có $$\lvert \det B \rvert = \lVert e_1 \rVert \dots \lVert e_n \rVert $$ ạ. Em có tìm qua tài liệu mà chưa tìm được cái này ạ.

[Konstante]

Vì $\det B = \det {}^tB$ nên $\left(\det B \right)^2 = \det B{}^{t}B$, mặt khác do các $e_i$ là trực giao nên $$B{}^{t}B =\begin{bmatrix}\lVert e_{1} \rVert^2 & & 0 \\& \ddots & \\ 0 & & \lVert e_{n} \rVert^2\end{bmatrix}$$Do vậy $\det B{}^{t}B = \lVert e_1 \rVert^2 \dots \lVert e_n \rVert^2$ và từ đó $\lvert \det B \rvert = \lVert e_1 \rVert \dots \lVert e_n \rVert$.

Bài viết đã được chỉnh sửa nội dung bởi Konstante: 18-01-2024 - 03:02