Math olympiad problem.

[Bennett Bellows]

How can I solve this math olympiad problem?
I am weak in math and have no idea where to start.
This task was issued by the department of mathematics of my university and it was not possible to find something similar on the Internet.
The task:
There is a matrix of dimension n×n.
The main diagonal is zeros.
The remaining numbers of the matrix are either 1 or 1980.
Prove that the rank of the matrix is either n-1 or n.

Thank you in advance!

 

[Deleted member 4993]

How can I solve this math olympiad problem?
I am weak in math and have no idea where to start.
This task was issued by the department of mathematics of my university and it was not possible to find something similar on the Internet.
The task:
There is a matrix of dimension n×n.
The main diagonal is zeros.
The remaining numbers of the matrix are either 1 or 1980.
Prove that the rank of the matrix is either n-1 or n.

Thank you in advance!

Please follow the rules of posting at this forum, enunciated at:

https://www.freemathhelp.com/forum/threads/read-before-posting.109846/

Please share your work/thoughts and context of the problem (what is the subject topic?) - so that we know where to begin to help you.

What is the definition of rank of the matrix?

 

[Bennett Bellows]

Please follow the rules of posting at this forum, enunciated at:

https://www.freemathhelp.com/forum/threads/read-before-posting.109846/

Please share your work/thoughts and context of the problem (what is the subject topic?) - so that we know where to begin to help you.

What is the definition of rank of the matrix?

1) Excuse me, but this is my first time on this site. I read this topic before asking a question. Could you point out my mistakes? I will gladly fix them.
2) Honestly, I do not have "my decision." I am familiar with matrices, but I have never encountered such complications as the dimension given by a constant. Also, I can’t imagine how to unequivocally prove what I need.
3) The rank of the matrix is the rank of the matrix =)

Rank (linear algebra) - Wikipedia

en.wikipedia.org

 

[Deleted member 4993]

1) Excuse me, but this is my first time on this site. I read this topic before asking a question. Could you point out my mistakes? I will gladly fix them.
2) Honestly, I do not have "my decision." I am familiar with matrices, but I have never encountered such complications as the dimension given by a constant. Also, I can’t imagine how to unequivocally prove what I need.
3) The rank of the matrix is the rank of the matrix =)

Rank (linear algebra) - Wikipedia

en.wikipedia.org

About the fifth paragraph in "read before posting" says:

Show some of your work or explain where you're stuck.

Your statement "The rank of the matrix is the rank of the matrix" tells me that you did not even read the Wiki article you have referred!!

What text-book did you follow when you became "familiar" with matrices? You should find definitions of rank and order of matrices in there.

 

[Bennett Bellows]

About the fifth paragraph in "read before posting" says:

Show some of your work or explain where you're stuck.

Your statement "The rank of the matrix is the rank of the matrix" tells me that you did not even read the Wiki article you have referred!!

What text-book did you follow when you became "familiar" with matrices? You should find definitions of rank and order of matrices in there.

At first I was afraid that I had not translated the concept of matrix rank into English, but after checking it turned out that everything was correct.
Rank is corresponds to the maximal number of linearly independent columns of martix.
Both in my language and in English.
Why are you asking about rank?

 

[Steven G]

How can I solve this math olympiad problem?
I am weak in math and have no idea where to start.
This task was issued by the department of mathematics of my university and it was not possible to find something similar on the Internet.
The task:
There is a matrix of dimension n×n.
The main diagonal is zeros.
The remaining numbers of the matrix are either 1 or 1980.
Prove that the rank of the matrix is either n-1 or n.

Thank you in advance!

What would the rank be if all the entries off the main diagonal was 1 and zeros on the main diagonal? What happens if we exchange a 1 with 1980? It is a start.

 

[Deleted member 4993]

At first I was afraid that I had not translated the concept of matrix rank into English, but after checking it turned out that everything was correct.
Rank is corresponds to the maximal number of linearly independent columns of martix.
Both in my language and in English.
Why are you asking about rank?

Because you did not show any work and stated:

"I am weak in math and have no idea where to start."

Since you do not have any idea where to start - we start with definitions of the subject matter.

 

[Bennett Bellows]

So, I checked all cases from 2x2 to 5x5, as well as some combined cases. It always turns out that the rank is n. What should I do next?

 

[Steven G]

So, I checked all cases from 2x2 to 5x5, as well as some combined cases. It always turns out that the rank is n. What should I do next?

Did you notice why you kept getting n? Looking at examples are very good but you need to gleam something from them so that you see why it will be true in general. If you have not seen any reason why it will work in all cases, then you should look at some more concrete examples.
You must show this for a general nxn matrix of the kind defined?

 

[Bennett Bellows]

Did you notice why you kept getting n? Looking at examples are very good but you need to gleam something from them so that you see why it will be true in general. If you have not seen any reason why it will work in all cases, then you should look at some more concrete examples.
You must show this for a general nxn matrix of the kind defined?

I checked some more examples and in all cases I got a rank equal to n. Yes, I have to prove it for the nxn matrix. All I have is the condition of the problem without any further explanation. I don’t understand how can I unequivocally prove that the rank will always be equal to n? I can check many options, but how to confirm this for all cases?

 

[Steven G]

I checked some more examples and in all cases I got a rank equal to n. Yes, I have to prove it for the nxn matrix. All I have is the condition of the problem without any further explanation. I don’t understand how can I unequivocally prove that the rank will always be equal to n? I can check many options, but how to confirm this for all cases?

Maybe you should try it by induction on n.
Is the statement of the theorem true for a 1x1 matrix? What will the 1x1 matrix look like?
Assume the statement is true for all nxn matrices.
Now show that it is true for (n+1)x(n+1) matrices

 

[Bennett Bellows]

Maybe you should try it by induction on n.
Is the statement of the theorem true for a 1x1 matrix? What will the 1x1 matrix look like?
Assume the statement is true for all nxn matrices.
Now show that it is true for (n+1)x(n+1) matrices

You strained my imagination =)
A 1x1 matrix will be 0, right? Because only the first number of the main diagonal remains. If so, then the rank of this matrix is 0 (i.e. n-1). Or am I wrong and will there be 1 or 1980? In this case, the rank is still n.
As for the matrix (n + 1) x (n + 1). How can I consider such a matrix? The first thing that came to mind was to take the 3x3 matrix and assume that (n + 1) = 3. The rank in this case would be 3 or (n + 1). Therefore, in matrices of the form (n + 1) x (n + 1) rank equal to (n + 1).

 

[Steven G]

A 1x1 matrix will be a matrix that has 1 entry and yes that entry would be 0. And yes, the rank would be 0.
How would you consider a (n + 1) x (n + 1) you ask. Well take a nxn matrix (which you assume has a rank of n or n-1) and add a row on the bottom and a column to the right. These 'additional entries' will have a single zero and 2n entries consisting of 1s and 1980s. How would the extra row and column affect the rank? That is what wanted you to see from your examples. Knowing to use induction was to be obvious!