The upper bound on the dimension of a trivial spectrum subspace: A "combinatorial" approach


Abstract: This post explains a "combinatorial" idea indicated in "On the affine geometry of matrix spaces, and quadratic decomposition issues", written by Clément de Seguins Pazzis. The lemma and theorem mentioned were parts of the paper "Spaces of matrices with few eigenvalues" (Linear Algebra and its Applications, 2014). 

1. Preliminaries
   
   For simplicity, this post doesn't use the same notations as the original document. Let K be a field and denote by M(n, K) the set of all square matrices of size n over K. We can view M(n, K) as a linear space whose dimension is n^2. 
   For every matrix M belonging to M(n, K), denote by L(i, K) the i-th row of K for every i = 1, 2, ..., n and K(M) the (n - 1) x (n - 1) matrix whose (i, j)th entry is the same as the (i, j)th entry of M for all 1 <= i, j <= n - 1. In other words, K(M) is obtained from M by removing the last row and the last column. 
   The following type of matrix is simple but useful. For every 1 <= i, j <= n, denote by E(i, j) the matrix in M(n, K) such that the (i, j)th entry is one and all the other entries are zero. 
   Let V be a linear subspace of M(n, K). For every i = 1, 2, ..., n, denote by L'(i, V) the set of all matrices in M(n, K) whose j-th row is zero for every j different from i. A linear subspace V of M(n, K) is called a trivial spectrum subspace when no element of V has a non-zero eigenvalue in K. 

2. Main results
   
   Lemma: Let V be a trivial spectrum subspace of M(n, K). Then there exists an index i in {1, 2, ..., n} such that L'(i, V) = 0.
   Proof: We proof by induction on n. Firstly, note that the result is obvious if n = 1, since {0} is the only trivial spectrum subspace. If n > 1, assume that L'(i, V) is not {0} for all i. Denote by V' the subspace of V consisting of all matrices whose last row is zero. The linear subspace K(V) of M(n - 1, K) is clearly a trivial spectrum one. By our induction hypothesis, we recover an index i <= n - 1 such that L'(i, K(V)) = 0. Since L(i, V) is not {0}, there is a matrix in L(i, V) such that the i-th row is not zero. However, L'(i, K(V)) = 0, thus the only nonzero coefficient in the i-th row is the (i, n)th entry. As K is a field and V is a vector space, this implies E(i, n) is in V. 
   By means of conjugation with permutation matrices, the n-th row can be swapped with any other row. Moreover, if V is a (trivial spectrum) subspace, then for every invertible matrix P, P^(-1)VP is also a (trivial spectrum) subspace. Let P be the matrix whose left multiplication swaps the n-th row and the j-th row. More rigorously and technically: 
   - The (n, j)-th and the (j, n)-th entries of P are 1. 
   - The (i, i)-th entry is one for every i different from j, n. 
   - All the other entries are zero.
   If V is a trivial spectrum subspace such that L'(i, V) is not {0} for all i, P^(-1)VP is also a trivial spectrum subspace and L'(i, P^(-1)VP) is not {0} for all i. As a result, there exists i(2) such that E(i(2), n) is an element of P^(-1)VP and E(i(2), j) is an element of V. Set f(j) = i(2). 
   Perhaps here comes the "combinatorial" stage. Iterate the following procedures until a number appears twice: pick a random number a(0) in {1, 2, ..., n}. For every j >= 1, set a(j) = f(a(j - 1)). After a certain number of times, there must be a number that appears at least twice in the sequence a(0), a(1), a(2), ...

Figure 1: How the "cycle" is found

   This yields a "cycle" j(1), j(2), ..., j(k), where j(1), j(2), ..., j(k) are different numbers, such that f(j(1)) = j(2), f(j(2)) = j(3), ..., f(j(k - 1)) = j(k), f(j(k)) = j(1). Note that f is not necessarily a bijection. The matrix E(j(2), j(1)) + E(j(3), j(2)) + ... + E(j(k), j(k - 1)) + E(j(1), j(k)) is also an element of V and (1, 1, ..., 1) is its eigenvector with respect to the eigenvalue 1, which is absurd. 

   Theorem: Let V be a trivial spectrum subspace of M(n, K). Then the dimension of V is smaller than or equal to 1/2*n*(n - 1). 
   Proof: Again, we prove by induction on n. Without loss of generosity, we can assume that L'(n, V) = 0. Infact, this can be done thanks to conjugation with a permutation matrix, as mentioned in the previous lemma. Consider the linear subspace W of V consisting of matrices whose (i, n)-th entry is zero for all i <= n - 1. Since L'(n, V) = 0, we have dim(W) = dim(K(W)), since a basis of W can be "induced" so as to obtain a basis of K(W). Moreover, K(W) is a trivial spectrum subspace, thus its dimension is at most 1/2*(n - 1)*(n - 2). It is obvious that dim(V) <= dim(W) + (n - 1). Moreover, dim(W) + (n - 1) = dim(K(W)) + (n - 1) <= 1/2*(n - 1)*(n - 2) + (n - 1) = 1/2*n*(n - 1). The proof is complete. 

Nhận xét

Đăng nhận xét

Bài đăng phổ biến từ blog này

Trước khi đi du học ngành toán tại Đức

Hình ảnh
Bài viết này tổng hợp những câu chuyện mang tính cá nhân về quá trình tôi chuẩn bị cho chuyến du học tại Đại học Bonn (Đức), một ngôi trường khá danh tiếng về ngành toán. Tôi đã chia sẻ khá đầy đủ những kinh nghiệm hữu ích cho mọi người trong  quyển guideline này , do đó trong bài viết này tôi sẽ đề cập đến những khía cạnh khác, chẳng hạn như trải nghiệm của tôi với các giáo sư ở Đức, hướng nghiên cứu của bản thân, hay là cả những câu chuyện mang tính giải trí cực cao.  1. Trước khi có ý định đi Đức, tôi KHÔNG BIẾT GÌ về Đại học Bonn và những trường khác ở Đức      Hồi năm thứ 1 và năm thứ 2, tôi chỉ tập trung học chứ gần như không tìm hiểu về các nhà toán học cũng như nơi công tác của họ. Lúc đó tôi chỉ thấy các trường ở Mỹ hấp dẫn vì có khá nhiều hướng nghiên cứu, hơn nữa hầu hết các trường đều có các giáo sư làm về đại số  và tổ hợp , những lĩnh vực tôi yêu thích nhất vào lúc đó. Tôi cũng biết rằng  Giáo sư Phan Thành Nam là một trong những cựu si...
Đọc thêm

Some remarkable statistics about the major of (pure) mathematics at several universities in the world

Hình ảnh
1. The number of PhD/Graduate students at some US universities    Many US universities indicated all of their graduate students on their websites. For example, the following image shows the list of graduate students in mathematics at Harvard University.     Based on these lists, I just counted the number of graduate students at some universities and got the following result(s): MIT has 122 students, Cornell University has 80 students, Texas A&M University has 105 students, Stanford University has 65 students, Harvard University has 64 students, Yale University has 46 students, University of Utah has 90 students, The University of Chicago has 81 students, City University of New York has 76 students and University of California, Berkeley (UCB) has 175 students.  2. The number of PhD/Graduate students from several universities who later became speakers at International Congress of Mathematicians    Being invited at International Congress of Mathe...
Đọc thêm

Some interesting facts about Vietnamese

Here is a collection of interesting facts about the language of Vietnamese (tiếng Việt) that I just found out when talking to my friends, who are all Europeans, in Bonn (Germany).  1. In Vietnamese, grandson and nephew are called the same (cháu trai). Similarly, granddaughter and niece are also called the same (cháu gái).  2. In Vietnamese, you can use the same pronoun "em" to call your younger sibling, no matter whether it is your younger brother or your younger sister. Similarly, this pronoun can be used to call someone who is just a few years younger than you, no matter whether this person is a man or a woman.  3. However, when referring to your older sibling, you must use the pronoun "anh" to call your older brother and the pronoun "chị" to cold your older sister. Similarly, you can use the pronoun "anh" to call a boy who is just a few years older than you and the pronoun "chị" to call a girl who is just a few years older than you. ...
Đọc thêm