uniolympiads Ελληνικά

IMC 1994, Day 1, Problem 1

a) Let AA be a n×nn \times n, n≥2n \ge 2, symmetric, invertible matrix with real positive elements. Show that zn≤n2−2nz_n \le n^2 - 2n, where znz_n is the number of zero elements in A−1A^{-1}.

b) How many zero elements are there in the inverse of the n×nn \times n matrix

A=(1111…11222…21211…11212…2⋯⋯⋯⋯⋯⋯1212……)?A = \begin{pmatrix} 1 & 1 & 1 & 1 & \dots & 1 \\ 1 & 2 & 2 & 2 & \dots & 2 \\ 1 & 2 & 1 & 1 & \dots & 1 \\ 1 & 2 & 1 & 2 & \dots & 2 \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ 1 & 2 & 1 & 2 & \dots & \dots \end{pmatrix}?
Original from the official PDF(13 points) a) Let A be a n × n, n ≥ 2, symmetric, invertible matrix with real positive elements. Show that z n ≤ n 2 − 2n, where z n is the number of zero elements in A −1 . b) How many zero elements are there in the inverse of the n × n matrix 1 1 1 1 ... 1  1 2 2 2 ... 2     1 2 1 1 ... 1    A =   ?  1 2 1 2 ... 2     ....................  1 2 1 2 ... ...  

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. Denote by aija_{ij} and bijb_{ij} the elements of AA and A−1A^{-1}, respectively. Then for k≠mk\ne m we have ∑i=0nakibim=0\sum\limits_{i=0}^n a_{ki}b_{im}=0 and from the positivity of aija_{ij} we conclude that at least one of {bim:i=1,2,…,n}\{b_{im}:i=1,2,\dots,n\} is positive and at least one is negative. Hence we have at least two non-zero elements in every column of A−1A^{-1}. This proves part a). For part b) all bijb_{ij} are zero except b1,1=2b_{1,1}=2, bn,n=(−1)nb_{n,n}=(-1)^n, bi,i+1=bi+1,i=(−1)ib_{i,i+1}=b_{i+1,i}=(-1)^i for i=1,2,…,n−1i=1,2,\dots,n-1.

Transcribed from the official solutions, page 2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?