Partial Orders
matrix
IMO Shortlist
combinatorics

A cake has the form of an $ n$ x $ n$ square composed of $ n^{2}$ unit squares. Strawberries lie on some of the unit squares so that each row or column contains exactly one strawberry; call this arrangement $\mathcal{A}$.

Let $\mathcal{B}$ be another such arrangement. Suppose that every grid rectangle with one vertex at the top left corner of the cake contains no fewer strawberries of arrangement $\mathcal{B}$ than of arrangement $\mathcal{A}$. Prove that arrangement $\mathcal{B}$ can be obtained from $ \mathcal{A}$ by performing a number of switches, defined as follows:

A switch consists in selecting a grid rectangle with only two strawberries, situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle.

Let's change the condition to an analogous one: every grid rectangle with one vertex at the bottom right corner contains no fewer strawberries from $ A$ than $ B$. We must prove we bring $ A$ to $ B$ by some switches.

Write $ P\leq Q$ if every grid rectangle with one vertex at the bottom right corner contains no fewer strawberries from $ Q$ than $ P$. Then $ B\leq A$. We prove that we can perform a switch such that $ A$ goes to $ C$ and $ B\leq C$ and $ C<A$. We cannot perform infinitely many switches and thus we will end up with the arrangement $ B$ of strawberries. Let's place $ x$ instead of a strawberry on arrangement $ A$ and an $ o$ instead of a strawberry on arrangement $ B$. If $ x$ coincides with $ o$ we can remove the row and column containing them and reason by induction.

Note that if we have a rectangle $ MNPQ$ with $ M$ the lower-left corner and $ x$ in $ M,P$ then we can perform a switch in this rectangle unless there exists a point $ K$ inside it (not on sides $ NP,PQ$) such that the rectangle with one corner in $ K$ and one in the bottom-left corner contains the same number of $ x$ and $ o$.

Assume now that we cannot do any switch. We shall pick up a point $ K$ containing an $ x$ with the following property: the $ o$ in the row of $ K$ is to the left of $ x$ and every $ x$ or $ o$ found in the row below $ K$. We prove that from each $ K$ we may find a point $ K'$ with the same property above $ K$. This will yield a contradiction, as we must stop. Note that to begin we just take the $ x$ in the bottom row.

Let $ O$ be the lower-left corner.

Pick up now such a point $ K$. Assume there is an $ o$ in the point $ L$ to the right of $ K$. Then the rectangle $ R$ cornered in $ O$ and with height $ n$ and ending in the column of $ L$ must contain the same number of $ x$ as $ o$. It is easy to conclude from the property of $ K$ that there exists an $ o$ which is single in his row of rectangle $ R$, and it is above $ K$. Let it be the bottom one with this property. Say $ o$ is in point $ J$. Then the $ x$ in its row is to the right of $ L$. Say it is in point $ H$. We cannot exchange $ K$ and $ H$. This means we can find a point $ Z$ inside the rectangle cornered in $ K$ and $ H$ such that the rectangle cornered in $ O$ and $ Z$ contains an equal number of $ x$ and $ o$. If this rectangle does not contain $ L$ we might again choose an $ o$ such that its row does not contain $ x$ and thus repeat the step, only this time we will go down a row. So we cannot repeat this step indefinitely. Thus we can assume that the rectangle cornered in $ O$ and $ Z$ contains $ L$.
Let's then take the subrectangle of it whose top row contains $ K$. Start increasing the height of the rectangle. If we add an $ x$ and no $ o$, then the position $ x$ will be the desired position above $ x$. Thus we can add $ x$ and $ o$ or just an $ o$. If we would add an $ o$, we would contradict the assumption that $ B<A$. Thus we add an $ x$ and an $ o$ or no $ x$ and no $ o$. If we add no $ x$ and no $ o$ it means the $ x$ and $ o$ in this row are farther to the right. Then $ x$ is to the left of $ o$ otherwise we would not have $ B<A$ so we can take $ x$ as the position we seek. So we add $ x$ and $ o$ every time. This is possible of course only then the rectangle has $ n$ columns. But this is impossible, as the rectangle cornered in $ Z$ must have stricly less columns than the rectangle cornered in $ H$, so less than $ n$. Contradiction.

QED

Some background to this problem for those who are interested:

This setup given the problems gives a partial order on the symmetric group $ S_n$ (the set of permutation of $ n$ elements). This is in fact a well known order called the [b]Bruhat order[/b], which can be defined in general for Coxeter groups. The problem, then, is equivalent to a classic criterion for comparing two permutations in the Bruhat order of the symmetric group. For more information, see Combinatorics of Coxeter Groups by  Björner and Brenti (in particular, the criterion appears as Theorem 2.1.5)

Someone's been doing his homework for Stanley's class ;).  (Unlike me ... bother!)

Sorry if this is just equivalent to the stuff above, but...

Define the permutations $\sigma_A$ and $\sigma_B$ so that the strawberries in $A$ lie in squares $(i,\sigma_A(i))$ and those in $B$ lie in squares $(i,\sigma_B(i))$ (for $1\le i\le n$). (We use the matrix convention here for coordinates. [b]Edit for clarification:[/b] $(x,y)$ is in the $x^{th}$ row and $y^{th}$ column, where $(1,1)$ is the upper left corner.) Let $[m]=\{1,2,\ldots,m\}$ for positive integers $m$.

Noting that we can only perform finitely many operations on $A$ (the first row can only be finitely operated on, so after the first has been used up the second can only be finitely operated on, etc.), consider the following algorithm:

[list]1. If $\sigma_A(i)\ge \sigma_B(i)$ for $1\le i\le n$, then $\sigma_A=\sigma_B\implies A=B$, so stop. Otherwise, take the smallest $1\le k\le n$ such that $\sigma_B(k)>\sigma_A(k)$.

2. Because $\sigma_B(k)>\sigma_A(k)$, the rectangle $[k]\times[\sigma_A(k)]$, which contains at least as many strawberries in $B$ as in $A$, must contain some $(j,\sigma_B(j))$ (where $1\le j\le k-1$) such that $\sigma_B(j)\le \sigma_A(k)<\sigma_A(j)$ (by the minimality of $k$, $\sigma_B(i)\le \sigma_A(i)$ for all $1\le i\le k-1$, so we need at least one $i$ to negate the effects of $\sigma_B(k)>\sigma_A(k)$).

3. We can now go back to step 1 with $\sigma_{A'}=\sigma_{A}\begin{pmatrix}j&k\end{pmatrix}$, since each rectangle with a vertex at $(1,1)$ contains at least as many strawberries in $B$ as in $A'$.

Indeed, suppose to the contrary that there exists a rectangle $[u]\times[v]$ that contains more strawberries in $A'$ than in $B$. Since we simply moved strawberries from $(j,\sigma_A(j)),(k,\sigma_A(k))$ to $(j,\sigma_A(k)),(k,\sigma_A(j))$, we cannot have $u\not\in[j,k)$ or $v\not\in[\sigma_A(k),\sigma_A(j))=[\sigma_A(k),\sigma_{A'}(k))=[\sigma_{A'}(j),\sigma_A(j))$ or else $A'$ and $A$ have the same number of strawberries in $[u]\times[v]$ (i.e. either neither exchange matters in the first place, or the exchanges cancel out), which is of course no more than the number $B$ has. On the other hand, if $j\le u<k$ and $\sigma_A(k)\le v<\sigma_A(j)$, then by the minimality of $k$ (for all $1\le r\le k-1$, $|A\cap\{r\}\times[v]|\le|B\cap\{r\}\times[v]|$ since $\sigma_A(r)\ge\sigma_B(r)$) and the fact that $\sigma_B(j)\le \sigma_A(k)=\sigma_{A'}(j)<\sigma_A(j)\le v$,
\begin{align*}
0
&< |A'\cap[u]\times[v]|-|B\cap[u]\times[v]| \\
&=\sum_{r=1}^{u}|A'\cap\{r\}\times[v]|-|B\cap\{r\}\times[v]| \\
&=|A'\cap\{j\}\times[v]|-|B\cap\{j\}\times[v]|+\sum_{1\le r\ne j\le u}|A\cap\{r\}\times[v]|-|B\cap\{r\}\times[v]| \\
&\le|A'\cap\{j\}\times[v]|-|B\cap\{j\}\times[v]| \\
&= 1-1 \\
&= 0,
\end{align*}a contradiction.[/list]

Because the algorithm cannot go on forever (as noted above, we can only perform finitely many operations on $A$), we're done.

[quote="math154"]the rectangle [k]\times[\sigma_A(k)], which contains at least as many strawberries in B as in A, must contain some (j,\sigma_B(j)) (where 1\le j\le k-1) such that \sigma_B(j)\le \sigma_A(k)<\sigma_A(j) (by the minimality of k, \sigma_B(i)\le \sigma_A(i) for all 1\le i\le k-1, so we need at least one i to negate the effects of \sigma_B(k)>\sigma_A(k)).[/quote]

It might just be me reading this incorrectly, but isn't $\sigma_{A}(k)>\sigma_{A}(j)$ necessary for a switch to occur if $k > j$?

I think this is slightly different: Let row number $i$ counted from the bottom have height $i$. Given an arrangement $\mathcal{C}$, we define the [i]height[/i] of each column as the height of the row that the strawberry in that column lies in. For example, if strawberries cover the bottom left-top right diagonal, the columns read from left to right have heights $1,2,3,\dotsc,n$ respectively. If we label the columns from left to right as $1,2,3,\dotsc,n$, we see that the allowed operation is equivalent to exchanging two columns, where the first one has lower height than the second, and such that there are no strawberries in the rectangled formed by the strawberries.

[b]We now show that you can place the columns in the correct place one by one:[/b] Take the first column in $\mathcal{B}$, with height $h$. If the first column in $\mathcal{A}$ also has height $h$ - then great, we can go on to the next column in $\mathcal{B}$. If not, there is some column $i>1$ in $\mathcal{A}$ with height $h$. We want to move this to the first column by using the operation: If column $i-1$ in $\mathcal{A}$ has lower height than column $i$, we can just swap these two columns. If the height of $i-1$ is greater than that of $i$, we consider column $i-2$ (in $\mathcal{A}$), and then $i-3,i-4$ and so on, until we find a column $k<i$ with height smaller than $i$ (why is this guaranteed to happen? :) ). Then we can just swap columns $i$ and $k$ since there are no strawberries inside the rectangle their strawberries form. Repeat until we have brought the column that was in position $i$ to the first position.

Now just apply the same algorithm to the second column in $\mathcal{B}$, and so on, until we have made $\mathcal{A}$ into $\mathcal{B}$.

We proceed by induction on $n,$ the base case $n=1$ being trivial. Call a rectangle good if it's top left vertex corresponds to the top left vertex of the cake, and say a cake $X$ majorizes $Y$ if every good rectangle in $X$ has at least many strawberries as in $Y.$

Let the strawberry in the first column of $\mathcal{A}$ have coordinate $y_A,$ and define $y_B$ similarly. Assuming that coordinates increase from left to right and from down to up, it is evident that $y_B \geq y_A,$ since otherwise the $1 \times y_A$ good rectangle in $\mathcal{B}$ contains no strawberries while the one in $\mathcal{A}$ does.

If $y_A=y_B,$ we may simply remove the first column and row $y_A$ and finish by the inductive hypothesis in the remaining $n-1\times n-1$ matrix. The premises still hold, as each row/column has exactly one strawberry and every good rectangle in $\mathcal{B}$ still majorizes its counterpart in $\mathcal{A}$ (the strawberry in the removed row/column is in both good rectangles or neither).

Now assume $y_A < y_B.$ Consider the rectangle with corners $(1,y_A), (n,y_B)$ and the following algorithm:
- Let $(x, y_C)$ be a strawberry such that $y_A < y_C \leq y_B$ and $x$ is minimal.
- Perform a switch on $(1,y_A), (x,y_C).$ Now the strawberry in the first column is at $(1,y_C).$
- Repeat in the rectangle with corners $(1,y_C), (n,y_B).$

Clearly such a strawberry $(x,y_C)$ exists since there must be a strawberry in every row + well ordering principle. Furthermore, by minimality of $x,$ there is no strawberry in the rectangle with corners $(1,y_A), (x, y_C).$ Thus a switch is always possible. Finally, this algorithm clearly terminates, as $\{y_C\}_i$ is an increasing sequence bounded by $y_B.$ We have shown that this algorithm successfully moves the strawberry in the first column to its desired location in $\mathcal{B}.$ Let $\mathcal{A}'$ be the resulting cake after this algorithm. It remains to show that the matrix obtained by removing column $1$ and row $y_B$ in $\mathcal{A}'$ is majorized by its counterpart in $\mathcal{B}$ by the inductive hypothesis.

Evidently, majorization is transitive. Thus, since $\mathcal{B}$ majorizes $\mathcal{A}$ after deletion, it suffices to show that $\mathcal{A}$ majorizes $\mathcal{A}'$ after deletion. Indeed, note that the $y$ coordinate of an arbitrary strawberry that undergoes a switch can only decrease in the new configuration, which can, in turn, only decrease the number of strawberries in each good rectangle. We may now conclude.

I am not sure but I think that there exist a stronger problem.We have a matrix A n*n and we have 0,1,-1.We know that in every line and column is a uniquely 1,-1.A switch is defined as permutation of 2 lines or columns.Prove that we can make finitely switches such as we arrive at  a matrix -A.
Sorry for bad English.

Solution :

Consider the smallest (on inclusion) grid rectangle $P$ with one vertex on the top left corner and such that the number of strawberries in $P$ of $B$ $>$ then number of strawberries in $P$ of $A$. So easy to check that there is a strawberrie in the bottom right vertex of $P$ in $B$ and no such strawberry in $A$. Now there exist and a unique switch of $A$ such that a resulting matrix $A'$ will have a strawberry in the bottom right vertex of $P$. Not hard to check that $A<A'\leq B$. So reapiting this procedure we finally will get matrix $B$. Done

Put $A$'s and $B$'s in an $n\times n$ table to represent the locations of the strawberries. Note that if a cell contains both $A$ and $B$, we can remove the row and column it is in and induct down. Hence, suppose that every cell contains at most one letter. We will describe a series of switches that will bring the $A$ in the first column to the $B$ in the first column, after which we may remove these strawberries and their row and column and induct down. Number the rows and columns from $1$ to $n$, with $(1,1)$ at the top left corner. Suppose that the $A$ and $B$ in the first column are at $(i,1)$ and $(j,1)$. By plugging in a cell $(x,y)$, we mean to check the condition that the rectangle with top left $(1,1)$ and bottom right $(x,y)$ has at least as many $B$'s as $A$'s. Plugging in $(i,1)$, tells us that $i>j$. Define the shortcake zone of the cake as the cells $(x,y)$ with $j\le x<i$. Let $(p,q)$ be a cell labeled with an $A$ in the shortcake zone with $q$ minimal. Then, we claim that performing a switch on $(i,1)$ and $(p,q)$ preserves the condition in the problem statement. Notably, any such switch decreases the size of the shortcake zone, so we eventually get $A$ and $B$ to coincide, as desired.

Now, let's prove the claim. Consider the function $f:\{1,2,\ldots,n\}^2\rightarrow\mathbb Z_{\ge0}$ with $f(x,y)$ defined as the number of $B$'s minus the number of $A$'s in the rectangle with top left corner $(1,1)$ and bottom right corner $(x,y)$. Performing a switch on $(u_1,v_1)$ and $(u_2,v_2)$ with $u_1>u_2$ and $v_1<v_2$ decrements $f(x,y)$ by 1 if $u_2\le x<u_1$ and $v_1\le y<v_2$ and does not change $f(x,y)$ otherwise. The condition is equivalent to $f(x,y)\ge0$ for all $(x,y)$, so it suffices to show that $f(x,y)\ge1$ for all $i\le x<p$ and $1\le y<q$. Suppose that $f(x,y)=0$ for some $x,y$ in those intervals. In the first column of the rectangle with top left $(1,1)$ and bottom right $(x,y)$, there is one $B$. Hence, in order for $f(x,y)=0$, there must be some column in the rectangle with an $A$. This $A$ cannot be in the shortcake zone, as that contradicts the minimality of $q$. Hence, there is at least one row above the shortcake zone. Now, let's check the condition for $(i-1,y)$. We lose at least one $B$ going from the $(x,y)$ rectangle to the $(i-1,y)$ rectangle, namely $(i,1)$. But we only lose cells in a part of the shortcake zone which by assumption has no $A$'s, so $f(i-1,y)<0$, contradiction. Hence, our algorithm works and we can match our strawberries.

Please check my solution :help: (This is most probably similar to the solution of [b]Stens[/b] or [b]G_U[/b])
[hide = Solution] Nubmer the rows $1, \cdots, n$ from up to down and the columsn $1, \cdots, n$ from left to right. Let $A[i][j]$ donote the cell at i-th column and j-th row. Also, if the rectangle condition holds, say $B$ [i]muggawuggamugga's[/i] $A$.

[b] Claim - 1[/b]: Let the strawberry at $n$th column of $A$ be at $i$-th row, add the strawberry at $n$-th column of $B$ be at $j$-th row. Then $i \leq j$
[hide = Proof] Suppose for the sake of contradiction, $i > j$. Now consider the box $C$ with the top corner $[1][1]$ and bottom right corner $[n-1][j]$. In $A$, the rectangle $C$ contains exactly $j$ strawberries (since the strawberry on the last column is strictly below $j$th row, the $j$ strawberries in the first $j$ rows are distributed over the first $n-1$ columns). But in $B$, the rectangle $C$ contains exactly $j-1$ strawberries (because for the exact same reason as above, in the rectangle spanned by $[1][1]$ and $[n-1][j-1]$ in $B$, there are exactly $j-1$ strawberries, and since the strawberry on the $j$th row is on the $n$-th column, that's not counted by this box).

But this clearly contradicts the[i]muggawuggamugganess[/i] of $B$ over $A$, so a contradiction ! [/hide]

Now, for a $n$ by $n$ grid $A$, let $\text{Squeeze}(A)$ denote the $(n-1)$ by $(n-1)$ grid obtained by taking all the squares spanned by $[1][1]$ from the top left to the $[n-1][n]$ to the bottom right, and deleting the row having no strawberry.

[b] Claim - 2 [/b] If $C$ [i]muggawuggamugga's[/i] $D$, then $\text{Squeeze}(C)$ [i]muggawuggamugga's[/i] $\text{Squeeze}(D)$.
(The proof is simple and a contradiction can't hold followsjust by taking cases on the squares above the deleted row in squares below the deleted row in both grids, and noticing where they maps when they're squeezed)

We proceed the final proof by induction on $n$, the base case $n= 1, 2$ being trivial to check by hand. Assume it's true for all [i]good[/i] (i.e satisfies the sudoku like stawberry distribution) $n-1$ by $n-1$ grids. We prove that it's true for all [i] good [/i] $n$ by $n$ grids. Pick two $n$ by $n$ grids $A$ and $B$ where $B$ [i]muggawuggamugga's[/i] $A$.

First we need to change $A$ to a grid $A'$ such that $\text{Squeeze}(A) = \text{Squeeze}(A')$ and strawberry position at last column of $A'$ is the strawberry position at last column of $B$. This following algorithm clearly works: (Let $i$, $j$ denote the strawberry row position at last column of $A$ and $B$ respectively) (sorry this is more clear to write in this way rather than to write in words)
[code] while (i <= j):
  switch A[n][i] and A[m_{i+1}][i+1] //the strawberry at (i+1)th row is at m_{i+1}th column
  i += 1 [/code]
Now, by the inductive hypothesis, there exists a sequence of switch which transforms $\text{Squeeze}(A')$ to $\text{Squeeze}(B)$. Perform the sequence of moves, but if needed skip over the deleted row which was excluded in squeezing $A'$ (adding the deleted row back doesn't makes switching invalid, so this works). So we're done ! [/hide]

First, we will represent each cake as a sequence of $n$ numbers, such that the $i$th number represents the row in which the strawberry at column $i$ is in. Let the sequences of $\mathcal{A}$ and $\mathcal{B}$ be $S_A$ and $S_B$ respectively. The precondition of the problem implies that the $j$th smallest number of the first $i$ numbers in $S_A$ is no less than that in $S_B$, for all $1\le i\le n$ and $1\le j\le i$. Furthermore, a swap can be interpreted as interchanging two originally inverted elements of $S_A$, as long as there exists no numbers between them which are numerically between them as well. This implies that we can swap two consecutive elements which are originally inverted - a move which we will refer to as [i]bubbling[/i]. Finally, note that swapping preserves the precondition.

Now, as the validity of the problem's statement only depends on the relative magnitudes of the numbers in the sequence, we can actually induct on $n$. Our base case of $n=1$ is trivial, so go immediately to the inductive step.

Suppose that $1$ is at position $a_1$ in $S_A$ and $b_1$ in $S_B$. Now, by the precondition applied at $i=a_1$, note that $b_1\le a_1$, so we can just bubble $1$ up in $S_A$ to get it to the correct location. Now, as $1$ is in the correct position after the bubbling, there is no need to move it anymore. Also, there are no remaining elements which define intervals which include $1$, so we can effectively ignore it for the remaining swaps. Finally, note that if we ignore the $1$ in both sequences, the remaining sequences of size $n-1$ still satisfy the precondition, so we can use the inductive hypothesis to swap the remaining elements to be in the same order as $S_B$, as desired.

Let the coordinate of the top left, top right, bottom left corner be $(1,1),(1,n),(n,1)$ respectively.
Let the coordinates of the strawberries in $\mathcal A$ be $(1,a_1),(2,a_2),...,(n,a_n)$ and the coordinates of the strawberries in $\mathcal B$ be $(1,b_1),(2,b_2),...,(n,b_n)$.

For any numbers $x_1,x_2,...,x_j$ and $i\leq j$ we let $\text{min}_i\{x_1,x_2,...,x_j\}$ be the $i^{th}$ smallest number among them.

Notice that
$$\text{min}_i\{a_1,...,a_j\}\geq\text{min}_i\{b_1,...,b_j\}\hspace{20pt}(1)$$
for all $1\leq i\leq j\leq n$. Otherwise we can pick the rectangle with opposite vertices $(1,1),(j,\text{min}_i\{a_1,...,a_j\})$, it contains $i$ strawberries in $\mathcal A$ but at most $i-1$ strawberries in $B$, contradiction.

Moreover, notice that the switching condition just means switching $a_{m_1},a_{m_2}$ where $a_{m_1}<a_{m_2}$ and $m_1>m_2$. We will prove by induction on $n$ that every two permutations $a_1,...,a_n$ and $b_1,...,b_n$ of a set $\{x_1,...,x_n\}$ satisfying $(1)$, will satisfy the condition stated, that is $(b_1,...,b_n)$ can be obtained from $(a_1,...,a_n)$ through switching.

Indeed, obviously $a_1\geq b_1$. Let $k$ be the smallest indices such that $a_k<b_k$.
Now suppose $a_k$ is the $p^{th}$ smallest number among $a_1,...,a_k$. Let
$$A_1=\{\text{min}_i\{a_1,...,a_k\}:i> p\}$$
and $$A_2=\{\text{min}_i\{a_1,...,a_k\}:i\leq p\}$$
define $B_1,B_2$ similarly.

Now, notice that $b_k\in B_1$, therefore by pigeonhole principle there exists some $j$ such that $a_j\in A_1$ while $b_j\in B_2$. We swap $a_k$ and $a_j$. Let the sequence be $c_1,...,c_n$.

[color=#00f]Claim.[/color] $(1)$ still holds for the new sequence, that is
$$\text{min}_i\{c_1,...,c_m\}\geq \text{min}_i\{b_1,...,b_m\}$$
for all $1\leq i\leq m\leq n$
[u]Proof.[/u]
Notice that $\{c_1,...,c_m\}=\{a_1,...,a_m\}$ unless $k\leq m<j$. If $k\leq m<j$ then notice that $a_q\geq b_q$ for all $1\leq q\leq m$, so it is obvious. $\blacksquare$

Therefore, we can continue to carry out this procedure, it is easy to see that it must end, and in that situation, the two sequences must be equal, so we are done.

Impose a coordinate system on the cake, with the top left corner square being $(1,1)$, the bottom left being $(1,n)$ and the top right being $(n,1)$. Refer to a rectangle with one vertex at the top left corner and the bottom right corner at the bottom right corner of square $(x,y)$ the "$(x,y)$-rectangle". Now consider the position of the strawberry in each column in $A$ and $B$. Call a strawberry an "up-berry" if the position in $B$ is higher than $A$, a "down-berry" if the position is lower, and a "stay-berry" if the position is the same.
Now, I will present an algorithm for decreasing the number of down-berries, supposing that at least one exists. Suppose there exists some down-berry $S$ (for strawberry) that is at $(x,a)$ in $A$ and $(x,b)$ in $B$, with $b>a$. By considering the $(x,a)$-rectangle and the $(x,a-1)$-rectangle, it follows that there exists some up-berry to the left of $S$ that goes from $(x_1,a_1)$ in $A$ and $(x_1,b_1)$ for $B$, where $a_1\leq b$ and $b_1\geq a$. If $b_1<a$, by considering the $(x,b_1)$-rectangle and $(x,b_1-1)$-rectangle, it then follows that there exists some up-berry located in a column to the left of $x_1$ that goes from $(x_2,a_2)$ to $(x_2,b_2)$ with $a_2\leq b_1$ and $b_2> b_1$. Repeating this, we can come up with some sequence $s_1,s_2,\ldots,s_k$ of up-berries
$$(x_1,a_1)\to (x_1,b_1),(x_2,a_2)\to (x_2,b_2),\ldots, (x_k,a_k)\to (x_k,b_k)$$
such that $a_1\leq b,b_1\geq a,x_1<x$ and for $1<n\leq k$, we have $a_n\leq b_{n-1}$, $b_n>b_{n-1}$, and $x_n<x_{n-1}$. Then we can perform the swapping operation on $s_1,s_2$, $s_2,s_3$, and so on until we swap $s_{k-1}$ and $s_k$. Then we swap $s_k$ and the down-berry $S$. By the inequality chain, all these operations are legal, and in the resulting cake $s_1,s_2,\ldots,s_k$ remain up-berries whereas $S$ becomes either an up-berry or a stay-berry. This concludes the algorithm.

Now note that if there are no down-berries, there are clearly no up-berries either (since the sum of the "movements" up and down between $A$ and $B$ must be zero), so once we run the above algorithm enough times to arrive at no down-berries, there will be no up-berries either and we will have reached $B$ from $A$. $\blacksquare$

This writeup is kinda bad because I rushed it. I don't think all of my inequalities are right but I'm too lazy to check.  :maybe: Hopefully you get the idea.

[quote=Mosquitall]I think that in my proof we also need to use next

$\textbf{Lemma :}$

A cake has the form of an $ n$ x $ n$ square composed of $ n^{2}$ unit squares. Strawberries lie on some of the unit squares so that each row or column contains exactly one strawberry; call this arrangement $\mathcal{A}$.

A switch of $\textbf{type 1}$ consists in selecting a grid rectangle with only two strawberries, situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle.

Also define a switch of type $\textbf{type 2}$ that consists in selecting a grid rectangle with two strawberries (maybe not unique), situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle.

Then for any switch $\sigma$ of $\textbf{type 2}$ there exist some switches $\sigma_1, \ldots ,\sigma_k$ of $\textbf{type 1}$ so that $\sigma = \sigma_1\sigma_2\ldots\sigma_k$.[/quote]

After we have this we can put the strawberry in the first row in it's correct position and induct down.

There is a bijection from strawberry arrangements to permutations of $[n]$. We biject in the following manner: Let $\sigma_i$ be one more than the number of cake squares above the strawberry on the $i$th column from the left. For example, in the following arrangement, $\sigma=(\sigma_1,\sigma_2,\sigma_3,\sigma_4)$ is $(4,1,2,3)$.

[center][img width=30]https://media.discordapp.net/attachments/986049049834713139/1113627762343813140/ISL2006C4.png?width=884&height=888[/img][/center]

Call $\sigma$ the characteristic permutation of the arrangement. Let $\sigma(\mathcal{A}), \sigma(\mathcal{B})$ denote the characteristic permutations of $\mathcal{A}$ and $\mathcal{B}$, and let $\sigma_i(A)$ be the $i$th term of that sequence.

Let $f_{\mathcal{C}}(x,y)$ where $1\le x,y\le n$ and $\mathcal{C}$ is a strawberry arrangement be the number of strawberries in the rectangle that is $x$ long and $y$ tall. We see that $f_{\mathcal{C}}(x,y)$ is the number of values $i\le x$ such that $\sigma_i(\mathcal{C})\le y$.

Suppose for some $i$ that \[M=\text{max}(\sigma_1(\mathcal{A}),\sigma_2(\mathcal{A}),\dots, \sigma_i(\mathcal{A}))<\text{max}(\sigma_1(\mathcal{B}),\sigma_2(\mathcal{B}),\dots, \sigma_i(\mathcal{B}))\]
then $f_{\mathcal{B}}(i,M)\le i-1$ because there's at least one that's greater than $M$, and $f_{\mathcal{A}}(i,M)=i$. This is a contradiction since the $x$ by $y$ rectangle then contains less strawberries of $\mathcal{B}$ than $\mathcal{A}$. Therefore, we have \[\text{max}(\sigma_1(\mathcal{A}),\sigma_2(\mathcal{A}),\dots, \sigma_i(\mathcal{A}))\ge \text{max}(\sigma_1(\mathcal{B}),\sigma_2(\mathcal{B}),\dots, \sigma_i(\mathcal{B}))\]
for all $i$.

A switch is taking two indices $i\le j$ such that $\omega_i\ge \omega_j$ and switching the values $\omega_i$ and $\omega_j$. We claim that the above condition is sufficient to show that from $\omega(\mathcal{A})$ we can reach $\omega(\mathcal{B})$ from a series of such switches. We proceed by induction on $n$. Clearly, the result is true for $n=1$.

If there exists $i$ such that $\omega_i(\mathcal{A})=\omega_i(\mathcal{B})$ then we can ignore the index $i$ and subtract $1$ from each index $j>i$ and subtract $1$ from each value $x>\omega_i(\mathcal{A})$ and we are done by the induction hypothesis. Otherwise, there are no fixed points from $\omega_i(\mathcal{A})$ to $\omega_i(\mathcal{B})$.

We have $\omega_1(\mathcal{A})>\omega_1(\mathcal{B})$ so we can switch $\omega_1(\mathcal{A})$ and $\omega_1(\mathcal{B})$ in $\omega_1(\mathcal{A})$. The condition is still fulfilled since $\omega_i(\mathcal{A})$ only increases for $i\ge 2$ and there is a fixed point. We are done.


factorial
number theory proposed
number theory

Prove that for every $ n\in\mathbb{N}$ we have $ n$ different divisors $ d_i$ of $ n!$ such that $ d_1\plus{}d_2\plus{}...\plus{}d_n\equal{}n!$.

$ 3!\equal{}6\equal{}3\plus{}2\plus{}1$ satisfies the condition.
$ 4!\equal{}4*3!\equal{}4*3\plus{}4*2\plus{}4\equal{}4*3\plus{}4*2\plus{}3\plus{}1$ satisfies the condition.

Assume $ n\ge 3$.
If $ n!\equal{}d_1 \plus{} d_2 \plus{}...\plus{} d_{n\minus{}1} \plus{} 1$ satisfies the condition,then

$ (n\plus{}1)!\equal{}(n\plus{}1)*d_1 \plus{} (n\plus{}1)*d_2 \plus{}...\plus{} (n\plus{}1)*d_{n\minus{}1} \plus{} n \plus{} 1$  satisfies the condition.

But 2!=2 does not satisfy the condition.

I edited this article. :)

yes, it's correct
im sorry it was $ n\ge 3$  :oops:

another aproach can be using the fact that $ \sum\limits_{k\equal{}1}^n\frac{k}{(k\plus{}1)!}\equal{}1\minus{}\frac{1}{(n\plus{}1)!}$.

I wrote "$ (n \plus{} 1)! \equal{} (n \plus{} 1)*d_1 \plus{} (n \plus{} 1)*d_2 \plus{} ... \plus{} (n \plus{} 1)*d_{n \minus{} 1} \plus{} n \plus{} 1$ satisfies the condition".

But for $ 0 \le i \le \frac {n}{2} \minus{} 1$ , $ (n \plus{} 1)! \equal{} (n \plus{} 1)*d_1 \plus{} (n \plus{} 1)*d_2 \plus{} ... \plus{} (n \plus{} 1)*d_{n \minus{} 1} \plus{} (n \minus{} i) \plus{} (i \plus{} 1)$ also satisfies the condition.

So I propose the following open problem:

How many ways $ n! \equal{} d_1 \plus{} d_2 \plus{} ... \plus{} d_n$ exist satisfying the condition?

But I have no answer. :)


geometry
trigonometry
probability
calculus
number theory

I am homeschooling my gifted 9 year old son.  He will be entering 4th grade in the fall.  He just completed 7th grade math and is now at the stage where he should be entering the Pre-Alg/Algebra and beyond sequence... My question is: What would your recommendation be for him as far as sequencing?  I would love for him to use the "Art of Problem Solving" books (can they be used as a stand-alone curriculum book or are they more of a supplemental text? How long would they each take to go through?  i.e. would they fill a year, less or more?)... In what order would you suggest I fitting them all in?  Do they need to go in order or can we use the Number Theory book earlier?  Do you have any alternate ideas?  I would love any input!

4th- Pre-Algebra?
5th-Algebra 1?
6th-Counting & Prob.?
7th-Geometry?
8th-Number Theory?
9th-Algebra 2?
10th-Trig?
11th-Calc 1?
12th-Calc 2?

Our books are a full curriculum designed specifically for high-performing students.  We don't yet have a prealgebra book, but when your son is ready for algebra, then he's ready to start with our material.  In general, we recommend starting with Introduction to Algebra, and then moving on to Introduction to Counting & Probability and Introduction to Number Theory (in either order), and then Introduction to Geometry.  The counting and number theory books should only take a semester each, so you can combine them into one year.  (If your son is particularly avid about math, he may go through some of the books even faster.)  You might also split the Introduction to Algebra into two batches, working through Chapter 11 or 12 or so on the first pass, doing the counting and number theory, and then returning to finish the algebra.

Once the Introduction books are finished, move on to the Intermediate series: Intermediate Algebra, Intermediate Counting & Probability, Precalculus, and Calculus (probably in that order).


calculus
integration
real analysis
real analysis unsolved

http://www.mathlinks.ro/viewtopic.php?t=193490

This is the quotation from my topic of the above link.

[quote="Kouichi Nakagawa"][quote="gauss202"][quote="Doe John"]Use the formula $ \int_0^\infty \exp\left( \minus{} \alpha^2 t^2 \minus{} \frac {\beta^2}{t^2}\right) \, dt \equal{} \frac {\sqrt {\pi}}{2\alpha}\, e^{ \minus{} 2\alpha\beta}$
[/quote]

Is this a well known formula for you, or did you derive it specifically for this problem?[/quote]

This formula is Laplace Transform. $ \left(\text{Case by} \int_0^\infty e^{ \minus{} ax^2}F(x)dx \equal{} \int_0^\infty e^{ \minus{} at}\dfrac{F(\sqrt {t})}{\sqrt {t}}dt \right)$
$ \int_0^\infty \exp \left[ \minus{} c\left( \dfrac{x^2}{a^2} \plus{} \dfrac{b^2}{x^2} \right) \right] dx \equal{} \dfrac{a}{2}\sqrt {\dfrac{\pi}{c}}e^{ \minus{} \dfrac{2bc}{a}} \ \ (a, b, c > 0)$[/quote]


If a gasoline costs $ \$1.25$ per gallon, and your car has a 16-gallon gas tank that is $ \frac{3}{4}$ empty, how much will it cost to fill the tank?

If the gas tank holds 16 gallons, and it's 3/4 empty, that means there's 4 gallons of gas in it. Thus, the answer is $ 1.25 \times 4 \equal{} \boxed{5}$.

It's $ \frac{3}{4}\cdot{16}\equal{}12$ gallons to fill. Thus it's $ 12\cdot\$1.25\equal{}\$15$

Note izzy: That's the cost of the gasoline already in the tank. The quesitions asks how much money to fill.


USAMTS
AMC
USA(J)MO
USAMO
Vieta
geometry
congruent triangles

[b]Problem #1[/b] (07-08 USAMTS Round 1 #4)
In convex quadrilateral $ ABCD$, $ AB \equal{} CD$, $ \angle ABC \equal{} 77^\circ$, and $ \angle BCD \equal{} 150^\circ$. Let $ P$ be the intersection of the perpendicular bisectors of $ \overline{BC}$ and $ \overline{AD}$. Find $ \angle BPC$.

[b]Problem #2[/b] (BMO, proposed by the future)
There are $ 1985$ participants to an international meeting. In any group of three participants there are at least two who speak the same language. It is known that each participant speaks at most five languages. Prove that there exist at least $ 200$ participants who speak the same language.

depends on where P is.

If its inside its 180-43=137 degrees but if its outside its 47.
its alot of congruent triangles and stuff...and also angle chasing with 90 degree triangles.

okay somebody's gotta give me a hint for #1 I CAN'T GET IT

anyway this took five minutes to do:

[b]Problem #3[/b] (1984 USAMO #1, proposed by mwpl11)
Two roots of the real quartic $ x^4 \minus{} 18x^3 \plus{} ax^2 \plus{} 200x \minus{} 1984 \equal{} 0$ have product $ \minus{} 32$. Find $ a$.

hmm.. again, could someone estimate what I might've gotten on the USAMO with this err *proof*? (hopefully not zero :D)

[hide="sorry it looks long"]
thanks again for the clarification, mwpl

Let $ r_1$, $ r_2$, $ r_3$, and $ r_4$ represent the four roots of the quadratic.

Using Vieta's:
\[ r_1r_2r_3r_4 \equal{} \minus{} 1984
\]

\[ r_1r_2r_3 \plus{} r_1r_2r_4 \plus{} r_1r_3r_4 \plus{} r_2r_3r_4 \equal{} \minus{} 200 ... (1)
\]

\[ r_1r_2 \plus{} r_1r_3 \plus{} r_1r_4 \plus{} r_2r_3 \plus{} r_2r_4 \plus{} r_3r_4 \equal{} a ... (2)
\]

\[ r_1 \plus{} r_2 \plus{} r_3 \plus{} r_4 \equal{} 18 ... (3)
\]
We are given:
\[ r_1r_2 \equal{} \minus{} 32 ... (4)
\]
Therefore we can conclude
\[ r_3r_4 \equal{} 62 ... (5)
\]
Note that equation $ (2)$ can be simplified:
\[ r_1r_2 \plus{} r_1r_3 \plus{} r_1r_4 \plus{} r_2r_3 \plus{} r_2r_4 \plus{} r_3r_4
\]

\[ \equal{} \minus{} 32 \plus{} r_1r_3 \plus{} r_1r_4 \plus{} r_2r_3 \plus{} r_2r_4 \plus{} 62
\]

\[ \equal{} 30 \plus{} (r_1 \plus{} r_2)(r_3 \plus{} r_4)
\]
We will find the values $ (r_1 \plus{} r_2)$ and $ (r_3 \plus{} r_4)$ so we can plug them in:

Multiplying $ (3)$ by $ (4)$ and subtracting $ (1)$ we get:
\[ r_1^2r_2 \plus{} r_1r_2^2 \minus{} r_1r_3r_4 \minus{} r_2r_3r_4 \equal{} \minus{} 376
\]
Substituting,
\[ \minus{} 32(r_1 \plus{} r_2) \minus{} 62(r_1 \plus{} r_2) \equal{} \minus{} 376
\]
Solving, we get
\[ \boxed{r_1 \plus{} r_2 \equal{} 4}
\]
It works similarly with equation $ (5)$. Multiplying $ (3)$ by $ (5)$ and subtracting $ (1)$,
\[ r_1r_3r_4 \plus{} r_2r_3r_4 \plus{} r_3^2r_4 \plus{} r_3r_4^2 \equal{} 1116
\]
Substituting,
\[ 62(r_3 \plus{} r_4) \plus{} 32(r_3 \plus{} r_4) \equal{} 1316
\]
Solving, we get
\[ \boxed{r_3 \plus{} r_4 \equal{} 14}
\]
Substituting the results into the simplified form of equation $ (2)$, the value of $ a$ equals:
\[ 30 \plus{} 4\cdot14 \equal{} \boxed{86}
\]
[/hide]

umm neither can i...apparently its only 47, i dont get why P cant be in the triangle (doesnt it matter where it is?)

easy problem, another logic problem
The professor tells Peter the product of two positive integers and Sam their sum. At first, nobody of them knows the number of the other.

One of them says: You can't possibly guess my number.
Then the other says: You are wrong, the number is 136.

Which number did the professor tell them respectively? Give reasons for your claim.

It can't be inside the quadrilateral. Say $ \overline{BC}$ is $ 0$. It then becomes an isosceles triangle with a vertex angle of $ 47^\circ$ with the perpendicular bisector of $ \overline{AD}$ bisecting the vertex angle.

As $ \overline{BC}$ is lengthened, $ m\angle DAB$ increases, and the perpendicular bisector, which is between the midpoint of $ \overline{BC}$ and $ D$, moves away from $ B$ and the midpoint of $ \overline{BC}$.

okay yeah this is all intuitive, so if anyone can actually prove this, please..

Old USAMOs = All Calculation.  Too easy.

http://www.usamts.org/Solutions/Solution4_1_19.pdf

There's your solution.


A king tours every square of an 8 x 8 board, visiting each square exactly once and returning to his starting position. Show that he made an even number of diagonal moves. [A king can move one square in any direction, horizontally, vertically or diagonally.]

[hide="Solution"]
It's pretty clear that he makes an even number of total moves (64), so it is sufficient to show that he makes an even number of non-diagonal moves.

Color the chessboard like a standard chessboard.  On a particular move, the king switches colors if and only if he makes a non-diagonal move.  Since he must return to the same color (in fact, the same square), he must make an even number of non-diagonal moves.
[/hide]


[b]a.)[/b] How should two right circular cylinders (with infinite altitude) be placed with respect to each other such that their curve of intersection is planar (i. e. their curve of intersection completely lies within a plane) ?

additional problems:

[b]b.)[/b] The same for the curve of intersection of a cylinder with a sphere.

[b]c.)[/b] When is the curve of intersection of two cylinders placed on two planes ?

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]introduction for the IMO ShortList/LongList project[/url] and regarding[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]solutions[/url]  :)


algebra
polynomial
inequalities
geometry
geometric transformation
calculus
derivative

Consider the polynomial $ P(x)\equal{}x^{3}\plus{}x^{2}\minus{}x\plus{}2$. Determine all real numbers $ r$ such that there exists a complex number $ z$ not in the reals such that $ P(z)\equal{}r$.

Hey, I didn't ask you to find all the roots of this equation!  :D

Read the question again.

In other words, we need to find real number values of $ P$ that can be achieved with non-real inputs.

[hide]$ x^{3}+x^{2}-x+2-r = 0 = y^{3}-\frac{4}{3}y+\left(\frac{65}{27}-r\right),\qquad y = x+\frac{1}{3}$

We now have the cubic in depressed form. This is helpful for calculating the discriminant. We want:

$ \Delta^{*}= 4p^{3}+27q^{2}> 0\implies 4\left(-\frac{4}{3}\right)^{3}+27\left(\frac{65}{27}-r\right)^{2}> 0$

First, find the roots of the equation:
$ \implies\left(\frac{65}{27}-r\right)^{2}=\frac{4 (4^{3})}{27 (3^{3})}=\frac{16^{2}}{27^{2}}\implies r-\frac{65}{27}=\pm\frac{16}{27}\implies r =\frac{49}{27},\; 3$

The extreme segments satisfy the inequality, but the inner segment does not; $ \boxed{\left(-\infty,\frac{49}{27}\right)\cup\left( 3,+\infty\right)}$
[/hide]

[b]Comment:[/b] While the discriminant of a cubic can be very helpful, it can be a lot to remember:
$ \Delta = 4b^{3}d-b^{2}c^{2}+4ac^{3}-18abcd+27a^{2}d^{2}$.
However, every cubic can be written in the form $ y^{3}+py+q,\; y = ax+b$. Since horizontal translation and scaling doesn't affect the nature of the roots, it suffices to remember the discriminant as:
$ \Delta^{*}= 4p^{3}+27q^{2}$
The above was achieved by using $ (a, b, c, d) = (1, 0, p, q)$ from the depressed cubic. This result is much easier to remember and equally useful.

[quote="cancer"]Consider the polynomial $ P(x) \equal{} x^{3}\plus{}x^{2}\minus{}x\plus{}2$. Determine all real numbers $ r$ such that there exists a complex number $ z$ not in the reals such that $ P(z) \equal{} r$.[/quote]
$ r\in\mathbb{R}\cap P(\mathbb{C}\minus{}\mathbb{R})$
let $ (x,y)\in\mathbb{R}\times (\mathbb{R}\minus{}\{0\})$
if $ r\equal{}P(x\plus{}iy)$ then $ P(x\plus{}iy)\in\mathbb{R}$ gives $ \minus{}y^{2}\plus{}3x^{2}\plus{}2x\minus{}1\equal{}0$
now you have to find $ S\equal{}\{x\in\mathbb{R}|\ 3x^{2}\plus{}2x\minus{}1>0\}$ (easy)
then $ r\in\{p(x\plus{}i\sqrt{3x^{2}\plus{}2x\minus{}1})|x\in S\}$

The critical points determine where you have 3 real roots. The interval is everything but that.

This is the same as asking when does $ P(x)\equal{}x^{3}\plus{}x^{2}\minus{}x\plus{}2\minus{}r$ have exactly one real root.

Think about a cubic. It has two local extrema. Three real roots occurs exactly when those extrema have opposite signs. Thus, if we take the derivative:

$ P'(x)\equal{}3x^{2}\plus{}2x\minus{}1$ and set it to zero, we obtain
$ 3x^{2}\plus{}2x\minus{}1\equal{}0$
$ x \equal{}\frac{\minus{}2\pm\sqrt{4\plus{}12}}{6}\equal{}\frac{\minus{}2\pm4}{6}\equal{}\minus{}1,\frac{1}{3}$

$ P(\minus{}1) \equal{} 3\minus{}r$, $ P(\frac{1}{3}) \equal{}\frac{1}{27}\plus{}\frac{3}{27}\minus{}\frac{9}{27}\plus{}\frac{54}{27}\minus{}r \equal{}\frac{49}{27}\minus{}r$.

As the leading coefficient is positive, $ P(\minus{}1)$ is the local maximum, and $ P(\frac{1}{3})$ is the local minimum. Thus, if we want $ P(\minus{}1)$ to be less than $ 0$, we need $ r>3$, and for $ P(\frac{1}{3})$ to be positive, we need $ r<\frac{49}{27}$. Thus, we have one real root on $ (\minus{}\infty,\frac{49}{27})\cup(3,\infty)$.

[quote="Hamster1800"]This is the same as asking when does $ P(x) \equal{} x^{3}\plus{}x^{2}\minus{}x\plus{}2\minus{}r$ have exactly one real root.[/quote]This is to prove that a good re-writing of the hypothesis solves half of the problem.


You either have to elaborate your problem statement or it is trivial. To make sense, we must start with co-prime sets $ \{q_i\}$ and $ \{p_i\}$, but then you find for any pair $ (s,t)$ infinitely many solutions, since $ Q^s,P^t$ are co-prime. The side-conditions $ \gcd(P,x_i)\equal{}\gcd(Q,y_i)\equal{}1$ are actually redundant.

[quote="quangpbc"]Let $ P \equal{} \prod_{i \equal{} 1}^np_i\;,p_i\ge n,Q \equal{} \prod_{i \equal{} 1}^mq_i,q_i\ge m$ and $ p_i,q_i$ are prime numbers.

Prove that has infinite pair $ (x_i,y_i)$ so that $ Q^sx_i \plus{} P^ty_i \equal{} 1\;s,t\in\mathbb{N}$ and $ \gcd(P,x_i) \equal{} \gcd(Q,y_i) \equal{} 1,\forall i$

 :)[/quote]
Really I don't understand your problem .
Because if $ \gcd(a,b)\equal{}1$ then the equation :$ ax\plus{}by\equal{}1$ has integer solution.
From this easy to check $ \gcd(x,b)\equal{}\gcd(a,y)\equal{}1$

[quote="hjbrasch"]??? this is what I stated ! the problem is trivial[/quote]
So I told that I don't  understand his problem.

this is straightforward by bezout's theorem...


Find the value of the real number $x$ satisfying the equation,

$(27)^{x-y}\times(45)^{x+y}=\sqrt{15}$


Hello All,
I have a correlation matrix
and i want to check if the matrix is a postive definite matrix, if not i want to make the matrix to be positive definite......

In actual i am trying to develop a c++ code to accomplish the above,....
through there are many online codes sources are there, i want to learn the concept and implement it by itself and unfortunatly i dont have any pure mathematics background.

so if some one could explain me the steps it would be of great help....

Thanks in advance.....

Regards
RK

What do you mean by "correlation matrix"? A covariance matrix is always at least positive semidefinite, and only fails to be positive definite if the random variables are linearly dependent - that is, if you can compute one of them by a linear formula of the other variables (in which case, you might as well leave that variable out of the description).

A matrix consisting of correlation coefficients is what you would get if you choose new units of measurement in which each variable had variance $ 1$ and then computed the covariances. Hence, we can say the same things that we said about covariance matrices - always positive semidefinite, positive definite if the random variables are linearly independent.

Or is what you want to do to create the matrix first, and then once you have the matrix, to construct (gaussian?) random variables with those covariances?

Hello kent

i am trying to do a monte carlo simulation for estimating risk.....

either we have c0-variance or co relation matrix.

what ever it may but, can you help me to to determine wether a given matrix is a positive definite and if not how to make it to be a positive definite.

will be great if someone explain me with a smal example matrix... please.....

Your matrix is symmetric already, of course. In fact, a correlation (or covariance) matrix is always at least positive semidefinite; the only question is whether it's singular. In a statistical context, that would indicate that some of your data is redundant, which can be dealt with by simply ignoring the redundant parts.

Theoretically, you could simply calculate the determinant- if it's nonzero, we're done. If you're working with real numerical data, on the other hand, small errors cause trouble when testing whether something is zero. We might want instead to look for matrices that are almost singular, and have a very small eigenvalue somewhere.
For this, something like the [url=http://en.wikipedia.org/wiki/QR_algorithm]QR algorithm[/url] might be appropriate.

This leads to an end result: we have that the original matrix $ A$ is of the form $ A\equal{}Q^TDQ$, where $ Q$ is an orthogonal matrix and $ D$ is a nonnegative diagonl matrix with entries in decreasing order. The first $ k$ entries of $ D$ are "big" and the rest are very close to zero. We then ignore all but the upper left $ k\times k$ submatrix of $ D$ and the first $ k$ rows of $ Q$/columns of $ Q^T$. These rows can be interpreted as linear combinations of the original data variables, and they're a basis for the interesting stuff. They're also uncorrelated, by construction.
We can use these rows to prune the original data of redundant variables: run row elimination on them. The pivot columns mark variables to keep, while everything else can be thrown out.

Thank You very much jmerry.......

is there any online resource to study more with more detailed examples

i am expecting some kind of step by step tutorials

Regards
RK

More generally assume $ A$ is a $ (n,n)$ symmetric real matrix.
The quickest method to see if $ A$ is SPD is the Cholesky's method (cf. Wikipedia):
if $ A$ is SPD then $ A\equal{}C^TC$ where $ C$ is triangular and has a positive diagonal; the cholesky 's method is an algorithm (in $ n$ steps) which gives $ C$; the complexity of this algorithm is in $ O(n^3)$. If the algorithm fails to work during one step then $ A$ is not SPD; else it is SPD.
But this method works correctly only if $ A$ is well conditionned.
Else the problem is much more complicate; we can use the decomposition $ A\equal{}QR$ (cf. jmerry) in order to calculate approximations of $ A$-eigenvalues.
$ A_1\equal{}RQ$ is similar to $ A$ and has the decomposition $ A_1\equal{}Q_1R_1$; $ A_2\equal{}R_1Q_1\equal{}Q_2R_2,\cdots,A_k\equal{}Q_kR_k$. When $ k$ tends to infinity we can read easily approximations of $ A$-eigenvalues in $ A_k$. The complexity of the $ QR$ decomposition is in $ O(n^3)$ but here we must use this decomposition many times.


How many 5-digit numbers have at least one 2 or one 3 among their digits?

Subtracting 7*8*8*8*8...idk what you're doing...

Because they need at least ONE 2 or ONE three..

[hide]A 5-digit number can have for its leftmost digit anything from 1 to 9 inclusive, and for each of its next four digits anything from 0 through 9 inclusive. Thus there are $9\times 10\times 10\times 10\times 10=90,\!000$ 5-digit numbers.

A 5-digit number with no 2 or 3 as a digit can have for its first digit 1 or anything from 4 through 9, and can have for each other digit any of those numbers or 0.

There are $7 \times 8\times 8\times 8\times 8=28,\!672$ such 5-digit numbers. Therefore the number of 5-digit numbers with at least one 2 or one 3 as a digit is $90,\!000-28,\!672=\boxed{61,328}.$
[/hide]

I don't get what you said AIME 15, snee did everything right

EDIT: Wait actually nvm right forum  :blush:

what you talking about bobert1 this is Gamebot

You said I don't get AIME 15 (before you edited) and I thought you meant AIME problem #15

[quote=econaxis]I don't understand what I did wrong...

$9000$ $4$ digit integers.
So there are $5$ places in between those integers that we can put a $2$ or a $3$.
Now lets take the first $4$ where the $2$ or $3$ is not in the leftmost digit.
So for each $2$ or $3$ in the digits, there are $9000$ possible $4$ digit numbers around it.
$4\cdot9000=36000$
Now for the $2$ or $3$ in the leftmost digit, then there are $10^4$ possible digits to the right.

Now, adding the values, $2\cdot\left(36000+10000\right)=\boxed{92000}$[/quote]

It's 5 digit numbers, not 4 digit number.

[quote=snee]Because the first digit (the 10thousands digit) can be anything other than 0, you have 9 choices for that one, because the rest can be anything 1-0 they each have 10 possibilities, so 9*10*10*10*10 possibilities for 5 digit numbers, 90,000 in otherwords.
But now you only want ones with 2's or 3's in them, which means take off 2 from each of the possibilities and subtract that from 90,000, which turns out to be 9*10*10*10*10 - 7*8*8*8*8 = 61,328[/quote]

There is nothing in the problem statement that the first digit can not be a zero.  What if the problem had said "how many 1-digit numbers..."; this logic says that 0 is not a one digit number.  I think it is.

[quote=tpgettys1]There is nothing in the problem statement that assures me that the problem's author meant "5-digit number greater than 10000".  00000 is a 5-digit number.[/quote]

By that logic, every number has any number of digits since you can add infinite zeroes to the front.
Do you think that's true?
For example, 219 could be a 3927367-digit number if you added 3927364 zeroes at the beginning.
if you search up "can a 5-digit number start with 0," you will see that all results say no
and if you search up "how many 5-digit numbers are there," then there are 90000, because from 10000 to 99999, subtracting 9999 from all numbers gives the numbers from 1 to 90000, which has 90000 numbers. you won't get 99999 as a result.

Every number has a unique decimal representation, and hence $02$, $002$, $0002$ are not valid representations of the number $2$.


function
trigonometry
calculus
real analysis
algebra unsolved
algebra

My question is maybe simple, but actually I don't know the answer.

Decide whether the function [tex]sin(1/x)[/tex] has the bounded variation in the interval [tex](0; 1)[/tex] or not (we mean the open interval)?

Thanks for a reply.

Of course not. Its variation on the interval $(\frac1{n\pi},\frac1\pi)$ is $2(n-1)$.

Pushing this a little more, we see that $f(x)=x\sin\left(\frac1x\right)$ has infinite total variation on $(0,1).$ Extend this function to the closed interval and you have an example of a continuous (in fact, uniformly continuous) function that is not of bounded variation.

Perhaps this belonged in the calculus-analysis forum?


Let $ A$ be a Jordan block of order $ n$ with some eigenvalue $ \lambda$ and $ T$ the operator on the space of $ n \times n$ matrices given by $ T(M) = AM-MA$. Find the Jordan form of $ T$.

I don't think there is a simple form? Because the characteristic equation of T(M) is often irreducible, thus the best description of the eigenvalues (i.e., the Jordan Form) is the characteristic equation itself, which is kind of trivial to find. It is, however, plausible that I have no idea what I'm talking about.

...what?

berman, I'm asking to find the Jordan form of the operator T, not of any particular T(M) in its range

mdk, wtf? that's ... not a form, that's an integer

Okay sorry that's better.

Is the answer $ diag(J_{2n-1},J_{2n-3},...,J_{3},J_{1})$, where $ J_{k}$ is the Jordan block of order $ k$ with eigenvalue 0?

It is an interesting result, but the work is just kind of bleargh. Maybe there's an slick way, but I'm not so good at this sort of stuff. Here is some work.
[hide]It is worth noting that λ is irrelevant and T(M) ends up having any given element equal to the difference of the element below it and to the left of it from M, where elements off the sides of the matrix are assumed to be zero. So if we use the set of $ n\cdot n$ matrices with all elements zero except a single 1 somewhere as a basis for T, we see that T is represented by the $ n^{2}\cdot n^{2}$ matrix with all elements zero except: (a) the subdiagonal has n blocks of n-1 negative ones each, separated by single zeros and (b) there is a diagonal of ones starting on the first row of the (n+1)st column. This because, if $ U_{ij}$ has just a single nonzero element-a one in the ith row and jth column, then $ T(U_{ij})$ has a negative one to the right of the ith row, jth column, and a positive one above it (if applicable). It is clear that this matrix representation of T follows. The actual details for finding N such that TN=NJ are rather yucky, but I think it is pretty routine to do so. I don't really feel like doing it. Certainly once such a matrix is found in the general case, the multiplications TN and NJ are easy since T and J are so zeroey. My only concern here is that it may be hard to then prove that N is invertible.[/hide]
Do you have a solution?

[quote="MysticTerminator"]I think so.

proof?

also was it a good problem or not[/quote]

I can't tell you if it is good or not because I have never heard of Jordan Blocks, eigenvalue, etc.  I assume it would be if I knew what it meant (explanation, please?).

http://mathworld.wolfram.com/JordanBlock.html

http://mathworld.wolfram.com/Eigenvalue.html

some linear algebra stuff.

that was a good exercise Mystic.

[quote="indianamath"]what the heck is a jordan block?

lol i'm a few years behind...[/quote]
Look at the post before you :roll:

[quote="jb05"]Is the answer $ diag(J_{2n \minus{} 1},J_{2n \minus{} 3},...,J_{3},J_{1})$, where $ J_{k}$ is the Jordan block of order $ k$ with eigenvalue 0?[/quote]

The question has been solved already. 5x is not a form.


inequalities
function
algebra
polynomial
inequalities proposed

Let $a,b,c$ be non-negative real numbers. Prove that

\[\frac{1}{(a+b)^{2}}+\frac{1}{(b+c)^{2}}+\frac{1}{(c+a)^{2}}+\frac{24}{(a+b+c)^{2}}\ge \frac{8}{ab+bc+ca}.\]

Yet if you can solve this one, general problem is easy  :lol:

To be frank, it is also my recent inequality in the section of symmetric inequalities with special equalities.

The idea is to express $a,b,c$ in terms of symmetric expressions of $a,b,c$: $p=a+b+c$, $q=ab+bc+ca$, and $r=abc$. The desired inequality takes the form
\[\Bigl(\frac{p^{2}+q}{pq-r}\Bigl)^{2}-\frac{4p}{pq-r}+\frac{24}{p^{2}}\geq\frac8q. \]
It is sufficient to prove that
\[\left(\frac{p^{2}}{pq-r}\right)^{2}+\frac{25}{p^{2}}\geq \frac6q+\frac{4p}{pq-r}. \]
By AM-GM inequality, $p^{4}/(pq-r)^{2}+25/p^{2}\geq 10p/(pq-r)$. Thus we need to show that
\[\frac{6p}{pq-r}\geq\frac6q. \]
But this obviously reduces to $6pq\geq 6pq-r$. Q.E.D

You can expect detailed solution and many more beautiful inequalities in my coming book when you are in Hanoi for IMO.

Nice solution, pvthuan.
[quote="hungkhtn"]
Yet if you can solve this one, general problem is easy  :lol:[/quote]
I think the first general problem is the following:

[i]For $t\ge 3$, the inequality holds[/i]
\[\frac{1}{(a+b)^{2}}+\frac{1}{(b+c)^{2}}+\frac{1}{(c+a)^{2}}+\frac{t(t+2)}{(a+b+c)^{2}}\ge \frac{2t}{ab+bc+ca}. \]
On the other hand, the following generalization is interesting and harder:

[i]For $0\le t\le 15$, the inequality holds[/i]
\[\frac{1}{(a+b)^{2}}+\frac{1}{(b+c)^{2}}+\frac{1}{(c+a)^{2}}+\frac{t}{(a+b+c)^{2}}\ge \frac{9+t}{4(ab+bc+ca)}. \]

The first generalization is solved in the same manner as what I did to the original one. Here is the solution for the second Vasc' generalization in my book (with Le Vi).

Put $p=a+b+c,$ $q=ab+bc+ca$, and $r=abc$. The desired inequality takes the form
\[\left(\frac{p^{2}+q}{pq-r}\right)^{2}-\frac{4p}{pq-r}+\frac t{p^{2}}\geq \frac{9+t}{4q}. \]
For simplicity, we choose $p=1$ and consider the function
\[f(r)=4q(1-2q+q^{2}+4r)+4qt(q-r)^{2}-(9+t)(q-r)^{2}\geq0. \]
If $0\leq q\leq \frac14$ then $f(r)\geq f(0)\geq0$. If $q\geq\frac14$, put $q=\frac13(1-x^{2})$, for $0\leq x\leq\frac12$, we have the result $r\geq (1+x)^{2}(1-2x)/27$ thus
\[f(r)\geq f\left( \frac{(1+x)^{2}(1-2x)}{27}\right), \]
denote $x_{0}: =\frac{(1+x)^{2}(1-2x)}{27}$ and compute
\begin{eqnarray*}f(x_{0})&=&\frac{64}{2187}t+\frac{32}{81}x^{2}+\frac{140}{729}tx^{4}-\frac{152}{2187}tx^{5}-\frac{140}{2187}tx^{6}+\frac{32}{729}tx^{7}-\frac{16}{2187}tx^{8}-\frac8{27}x^{4}\\ &&\qquad\qquad\qquad\qquad\qquad\qquad-\frac{64}{81}x^{3}-\frac{16}{81}x^{6}+\frac{56}{81}x^{5}+\frac{32}{2187}tx^{3}-\frac{352}{2187}tx^{2}\\ &=&-\frac{4(1+x)(2x-1)(x-2)^{2}(2tx^{4}-5tx^{3}+54x^{2}-3tx^{2}+8tx+4t)}{2187}. \end{eqnarray*}
Note that $54x^{2}\geq 3tx^{2}$ and $4t\geq 5tx^{3}$ so that the polynomial in the last bracket of the numerator is nonnegative. Therefor $f(r)\geq 0$.

[quote="hungkhtn"]Let $a,b,c$ be non-negative real numbers. Prove that
\[\frac{1}{(a+b)^{2}}+\frac{1}{(b+c)^{2}}+\frac{1}{(c+a)^{2}}+\frac{24}{(a+b+c)^{2}}\ge \frac{8}{ab+bc+ca}. \]

When does equal sign hold, please?

The equality occurs when one of the three numbers, $a,b,c$ is $0$, while $1=5ab$, $a+b=1$. Solving the equation $a(1-a)=\tfrac15$, which gives $a=\tfrac12(1\pm \sqrt{\tfrac15})$.

So $\Bigl(\tfrac12(1+\sqrt{\tfrac15}), \tfrac12(1-\sqrt{\tfrac15}),0\Bigl)$ or any permuations of that triple.


inequalities
geometry
circumcircle
function
inequalities solved

For a,b,c real numbers prove that

(a+b+c)^2 + 3(abc)^(2/3)  \geq 4(ab+bc+ca)

It isn't hard but I like it a lot.

Indeed , it is nice, but I like the following geometric interpretation:
   Of course, it is enough to prove it for a,b,c>0, since |ab+bc+ca|<=|a|*|b|+.... So, take a=x^2, b=y^2, c=z^2. Then the inequality can be written:
   (x+y+z)(x+y-z)(y+z-x)(z+x-y)<=3(xyz)^4/3. Of course, the only non-trivial case is when x,y,z are the sides of a triangle T of area S and circumradius R. In this case the inequality can be written (16S^2)^3<=27x^4y^4z^4, or 64S^3<=3sqrt(3)(xyz)^2. Since S=xyz/4R, the inequality becomes 3sqrt(3)R^3>=xyz, or sinX*sinY*sinZ<=3sqrt(3)/8 (X,Y,Z are the angles of the triangle), which holds by AM-Gm and the fact that sum sinX<=3sqrt(3)/2.

This is my solution. I hope it is correct.
Naturally as you said we can suppose a,b,c \geq 0

We have
a+b-c \geq 2 \sqrt ab -c

Now we use AM-GM inequality  x^(1/4)y^(3/4) \leq 1/4x +3/4y

with x=c^3 and y=(abc)^(2/3)

Then 4c \sqrt ab \leq c 2 +3(abc)^(2/3)

Finally (a+b-c) 2 -4abc \geq (2 \sqrt ab-c) 2 -4ab=c 2-4c \sqrt ab \geq -3(abc)^(2/3)

Nice indeed, but a little bit unnatural, don't you think? The solution is very nice, anyway.

[quote="manlio"]For a,b,c real numbers prove that

$(a+b+c)^2 + 3{(abc)}^{2/3}  \geq 4(ab+bc+ca)$

It isn't hard but I like it a lot.[/quote]

This is equivalent to: $a^2+b^2+c^2 + 3{(abc)}^{2/3}  \geq 2(ab+bc+ca)$.

So we may assume $a,b,c \geq 0$. Let $x^3=a^2, y^3=b^2,z^3=c^2$, then by Schur and AM-GM:

$a^2+b^2+c^2 + 3{(abc)}^{2/3} = x^3+y^3 + z^3 + 3xyz \geq xy(x+y) + yz(y+z)+zx(z+x) $

$\geq 2(xy)^{3/2} + 2(yz)^{3/2} + 2(zx)^{3/2} =2(ab+bc+ca)$.

as u said we can assume that a,b,c >=0
and also for the reason of homogenity we can also assume that a+b+c=1
(a+b+c)+3(abc)^(1/3)>=1+9abc  (GM-HM for ab ,bc and ac)
so it suffis to prove that 1+9abc>=4(ab+bc+ca)
it's equivalent to
2(a+b+c)+9abc>=1
let f(a)=2(a+b+c)+9abc-1
where b is constant and a is variable (of course c= 1-a-b)
so f'(a)=(4-9b)(a-c) and f"(a)=2(9b-4)
*******if 4-9b=0
so f(a)=f(0)>=0  (evident simple subtitution)
*******if 9b-4>0
f is convexe and the minimum is reached for a=c
f(a)=b(3b-1)/4>=0
*******if 9b-4<0
the function is concave and the maximum is f(0) and f(1-b) which are equals to 2(b+(1-b))-1=(2b-1)>=0
finally the proof is complete
i know that the proof is strange:)
but what can i do!
it's my brain body :)!


Let $B_k$ Bernoulli's number
Prove that if $p>2$ is a prime number then $(p-2)!\sum_{k=0}^{(p-1)/2}B_{2k}$ it's not an integer

see that [url=http://mathworld.wolfram.com/BernoulliNumber.html]if you don't know what's Bernoulli's number[/url].


vector
linear algebra
matrix
Gauss
search
symmetry
analytic geometry

Let $ K$ be an arbitrary field, and let $ A\in K^{n\times n}$ and $ B\in K^{n\times n}$. Prove that if the dimension of the vector space $ \left\{C\in K^{n\times n}\mid AC\equal{}CB\right\}$ is $ >n\left(n\minus{}1\right)$, then it is $ \equal{}n^2$.

Do we get that $ A\equal{}B\equal{}\lambda I$?

Yes, iff the dimension is maximal, i.e. $ n^2$.

Let us denote $ \left\{C\in K^{n\times n}\mid AC\equal{}CB\right\}\equal{}W$. We suppose that  $ \dim{W}>n(n\minus{}1)$.

We denote with $ E_{ij}$ the matrix, which has the $ (ij)$-th entry $ 1$ (identity for multiplication in $ K$) and all the other $ 0$ (identity for addition in $ K$). Since all the matrices $ E_{ij}$, when $ i$ and $ j$ run over $ \left\{1,2,\ldots, n\right\}$ are lineary independent and $ L\left\{E_{11},E_{12},\ldots,E_{nn}\right\}\equal{}K^{n\times n}$, they form the basis of $ K^{n\times n}$. Since $ \dim{W}>n(n\minus{}1)$, there are at most $ n\minus{}1$ of them, which are not in $ W$. Therefore there exists at least one row and one column of $ E$-s, which is in W. Let us say this is the $ i$-th row and $ j$-th column.

Now we use the condition for $ W$ and put $ E_{ik}\equal{}C$, where $ k$ runs over  $ \left\{1,2,\ldots, n\right\}$.

$ AE_{ik}\equal{}E_{ik}B$

$ \Rightarrow a_{1i}\equal{}a_{2i}\equal{}\cdots\equal{}a_{(i\minus{}1)i}\equal{}a_{(i\plus{}1)i}\equal{}\cdots\equal{}a_{ni}\equal{}0\\
b_{k1}\equal{}\cdots\equal{}b_{k(k\minus{}1)}\equal{}b_{k(k\plus{}1)}\equal{}\cdots\equal{}b_{kn}\equal{}0\\
a_{ii}\equal{}b_{kk}$

Therefore we get $ B\equal{}a_{ii}I$, where $ I$ is the identity matrix.

Now we again use the condition for $ W$ and put $ E_{kj}\equal{}C$, where $ k$ runs over  $ \left\{1,2,\ldots, n\right\}$ and also consider $ B\equal{}a_{ii}I$.

$ AE_{kj}\equal{}E_{kj}B\equal{}E_{kj}a_{ii}I\equal{}a_{ii}E_{kj}$

$ \Rightarrow a_{1k}\equal{}a_{2k}\equal{}\cdots\equal{}a_{(k\minus{}1)k}\equal{}a_{(k\plus{}1)k}\equal{}\cdots\equal{}a_{nk}\equal{}0\\
a_{ii}\equal{}a_{kk}$

Therefore we get $ A\equal{}a_{ii}I$.

Since $ AC\equal{}a_{ii}IC\equal{}Ca_{ii}I\equal{}CB$, for all $ C\in K^{n\times n}$, we conclude that $ W\equal{}K^{n\times n}$ and hence $ \dim{W}\equal{}n^{2}$.

Here another approach (using basically the same result you derived): If $ W$ has maximal dimension, then $ A\equal{}B$ and $ A$ is in the center of the algebra $ M_n(K)$ which is known to be the set of multiples of the unity matrix.

[quote="tmrfea"]We denote with $ E_{ij}$ the matrix, which has the $ (ij)$-th entry $ 1$ (identity for multiplication in $ K$) and all the other $ 0$ (identity for addition in $ K$). Since all the matrices $ E_{ij}$, when $ i$ and $ j$ run over $ \left\{1,2,\ldots, n\right\}$ are lineary independent and $ L\left\{E_{11},E_{12},\ldots,E_{nn}\right\} \equal{} K^{n\times n}$, they form the basis of $ K^{n\times n}$. Since $ \dim{W} > n(n \minus{} 1)$, there are at most $ n \minus{} 1$ of them, which are not in $ W$.[/quote]

Sorry, but no. You cannot conclude this from $ \dim W > n\left(n \minus{} 1\right)$.

[quote="Third Edition"]Here another approach (using basically the same result you derived): If $ W$ has maximal dimension, then $ A \equal{} B$ and $ A$ is in the center of the algebra $ M_n(K)$ which is known to be the set of multiples of the unity matrix.[/quote]

Either I don't understand something, or are you proving $ \dim W \equal{} n^2\Longleftrightarrow A \equal{} B \equal{} kI_n$ ? This wasn't a part of the problem (and is pretty easy anyway).

  darij

[quote="darij grinberg"]You cannot conclude this from $ \dim{W}>n(n\minus{}1)$. [/quote]

All $ E$-s which are not included in $ W$ are lineary independent to the basis of $ W$, since otherwise, they would have to be in $ W$, because $ W$ is a vector subspace of $ K^{n\times n}$, which means that all linear combinations of its base vectors are in $ W$. But if there would be more than $ n\minus{}1$ $ E$-s not included in $ W$, then adding them to the vectors from the basis of $ W$  would give us a lineary independent set from $ K^{n\times n}$, which would have more than $ n^{2}$ vectors. But there are at most $ n^{2}$ lineary independent vectors in $ K^{n\times n}$.

Can you give me a hint, where I am wrong, Darij?

$ V \equal{} {\bf R}^3$ has basis $ e_1, e_2, e_3$.  The subspace $ W \equal{} \{a e_1 \plus{} be_2 \minus{} (a \plus{} b)e_3 \mid a, b \in {\bf R}\}$ is a two-dimensional subspace, but all of our three basis vectors lie outside this subspace, whereas you claim that at most one of them may lie outside.  I think you are assuming the complement of a subspace is a subspace ;)  (Your claim also sounds really silly in the case that $ W$ is 1-dimensional.)

[quote]All $ E$-s which are not included in $ W$ are lineary independent to the basis of $ W$,[/quote]  [i]Each[/i] $ E$ not in $ W$ is independent of a basis of $ W$; it does not follow that all of them together are.

Thank you, JBL.

Now I see the problem in my previous reasoning. I was concluding the complement of the truth. So, if $ \dim{W} = n^{2} - n + k$, then there are at [b]least[/b] $ (n - k)$ $ E$-s, which are not in $ W$ and not at most.

But I think, I have the solution now. Since it is late in my country, I will write just the steps of my solution and explain them tomorrow.

If we put the basis of $ W$ in the matrix $ ((n^{2} - n + k)\times n^{2})$ and perform the Gauss elimination to reduce $ W$ into its canonical form, we get pivots in the first $ n^{2} - n + k$ columns. Therefore there exists a row (say $ i$) and a column (say $ j$) in $ n\times n$ matrix, for which there exists a vector in $ W$, which has $ (ik)$-th entry, where $ k\in \{1,2,\ldots, n\}$, equal to $ 1$ and all the others in $ i$-th row and $ j$-th column equal to $ 0$ and a vector, which has $ (kj)$-th entry (where $ k\in \{1,2,\ldots, n\}$) equal to $ 1$ and all the others in $ j$-th column and $ i$-th row equal to $ 0$. Therefore all vectors with any combination of $ 0$-s and $ 1$-s in $ i$-th row and $ j$-th column are in $ W$ and at most $ n-k$ other non-zero entries. By considering $ ij$-th entries of $ AC = CB$ when $ C$ runs over those combinations, we conclude that $ (ii)$-th entry of $ A$ equals to $ (jj)$-th entry of $ B$ and all the other entries in $ i$-th row of $ A$ and $ j$-th column of $ B$ equal to $ 0$. Now it remains to study the other entries of $ A$ and $ B$, by considering the $ ik$-th entries ( $ k\in \{1,2,\ldots,j - 1,j + 1,\ldots n\}$) of $ AC$ and $ BC$,  which give us that $ b_{kl} = 0$ ($ l\in \{1,2,\ldots,k - 1,k + 1,\ldots n\}$) and $ b_{kk} = a_{ii}$. Similarly we study the $ kj$-th entries ($ k\in \{1,2,\ldots,i - 1,i + 1,\ldots, n\}$) of $ AC$ and $ BC$ and conclude, that $ a_{lk} = 0$ ($ l\in \{1,2,\ldots,k - 1,k + 1,\ldots n\}$) and $ a_{kk} = a_{ii}$. Now we can conclude also that all the remaining entries in $ i$-th row of $ A$ and $ j$-th row of $ B$ equal to $ 0$. I hope it goes in the right way.

Hi tmrfea,
I don't see any proof in your last post; the Gauss elimination is not a change of basis; doing that you destroy $ A,B$. They do not exist any more.

   In the following I prove that we may assume $ A,B$ nilpotent.
$ f\equal{}A^{T}\bigotimes{I}\minus{}I\bigotimes{B}: C\rightarrow{AC\minus{}CB}$. See:
http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=664498693&t=137239
$ spectrum(f)\equal{}\{\lambda_i\minus{}\mu_j;i,j\leq{n}\}$ where $ spectrum(A)\equal{}\{\lambda_i\},spectrum(B)\equal{}\{\mu_j\}$. Here $ dim(ker(f))>n(n\minus{}1)$; then the order of multiplicity of the eigenvalue $ 0$ is $ >n(n\minus{}1)$. The max of the order of multiplicity, obtained only for $ spectrum(A)\equal{}spectrum(B)\equal{}\{a\}$, is equal to $ n^2$; the lower order in second position, obtained for $ spectrum(A)\equal{}\{a,\cdots,a,a\},spectrum(B)\equal{}\{a,\cdots,a,u\}$, is equal to $ n(n\minus{}1)$. Thus $ A\equal{}aI\plus{}N,B\equal{}aI\plus{}M$ where $ N,M$ are nilpotent. $ f(C)\equal{}NC\minus{}CM$.

Hi loup blanc. Thank you for your interest.

I didn`t write so clearly, what I meant by Gauss elimination, so I will try to be clearer now.

$ \{C\in K^{n\times n}\mid AC = CB\} = W$. We can represent elements of $ W$ as $ n\times n$ matrices.

[i]1. There exists a row ($ i$) and a column ($ j$) for which there exists an element $ C$ in $ W$, which has $ (i,k)$-th entry equal to $ 1$ (where $ k$ is an arbitary column), all the other entries in $ i$-th row and $ j$-th column equal to $ 0$ and at most $ n - s$ ($ s > 0$) other non-zero entries. Similarly there exists an element $ C$ in $ W$, which has $ (k,j)$-th entry equal to $ 1$ (where $ k$ is an arbitary row), all the other entries in $ i$-th row and $ j$-th column equal to $ 0$ and at most $ n - s$ ($ s > 0$) other non-zero entries.[/i]

Proof:
Let us say the dimension of $ W$ is $ n^{2} - n + s$ ($ s > 0$). Therefore the basis of $ W$ consists of $ n^{2} - n + s$ lineary independent vectors.  If we put them into the matrix $ (n^{2} - n + s)\times n^{2}$, where each column represents some entry of $ n\times n$ matrix, we can perform Gauss elimination and rearrange columns in such a way that we get pivots in the first $ n^{2} - n + s$ columns. The new vectors  are lineary independent and are all in $ W$. Therefore they are a new basis of $ W$. For a vector in $ i$-th row ($ ii$)-th entry equals $ 1$ and at most the last $ n - s$ ($ s > 0$) entries are not equal to $ 0$. Therefore for each new basis vector we know, that it has one entry in its matrix equal to $ 1$ and at most $ n - s$ other (but [b]same[/b] for all basis vectors) entries not equal to $ 0$. Since those unknown $ n - s$ entries "kill" at most $ n - s$ rows and $ n - s$ columns. The above statement follows.

[i]2. By considering ($ ij$)-th entries of $ AC$ and $ CB$  when $ C$ runs over the new basis (given in step $ 1$), we conclude that ($ ii$)-th entry of $ A$ equals to ($ jj$)-th entry of $ B$ and all the other entries in $ i$-th row of $ A$ and $ j$-th column of $ B$ equal to $ 0$.

3. Now it remains to study the other entries of $ B$, by considering the $ ik$-th entry $ ( k\in \{1,2,\ldots,j - 1,j + 1,\ldots n\})$ of  $ AC$ and $ CB$ when again $ C$ runs over new basis vectors (but it suffices to take those having one $ 1$ in $ i$-th row), which give us that $ b_{kl} = 0$ $ (l\in \{1,2,\ldots,k - 1,k + 1,\ldots, n\})$ and $ b_{kk} = a_{ii}$.

4. Similarly we study the other entries of $ A$, by studying the $ kj$-th entry ($ k\in \{1,2,\ldots,i - 1,i + 1,\ldots, n\}$) of $ AC$ and $ CB$, where $ C$ runs over the new basis vectors (but it suffices to take those having one $ 1$ in $ j$-th column)and conclude, that $ a_{lk} = 0$ ($ l\in \{1,2,\ldots,k - 1,k + 1,\ldots, n\}$) and $ a_{kk} = a_{ii}$. [/i]

Hence we can conclude $ A = B = a_{ii}I$ and $ \dim{ W} = n^{2}$.

I went over the same process again and I am quite sure it should be ok. Since this is a brute force method you can only verify this by taking a pencil and a blank paper and go through the upper steps calculating the entries of $ A$ and $ B$.  :)

Hi tmrfea,
I read your point 1). The proof is false because a linear combination of your columns do not give a linear combination of elements of $ W$. In my opinion you cannot solve this problem using this method.

In fact I think that this problem is very difficult.
Darij have you a hint ?

[quote="loup blanc"]I read your point 1). The proof is false because a linear combination of your columns do not give a linear combination of elements of $ W$. In my opinion you cannot solve this problem using this method. [/quote]
I do not make a linear combination of columns. I make a standard Gauss elimination of basis vectors of $ W$ in the standard basis of $ K^{n\times n}$, that is $ E_{11}, E_{12}, \ldots, E_{nn}$. I only rearrange columns and rows and add some multiple of some row to the other. In each step the rows are new basis vectors of $ W$.

Hi tmrfea,
you must work with columns. In particular, if you exchange 2 columns, then you are "dead".

Sorry for not replying earlier - I tried to understand tmrfea's proof, but somehow I kept petering out on step 1). tmrfea, can you please write it up less "dynamically" ("we can perform" etc.) and more formally? (It does look somewhat similar to mine proof, I just don't understand it...)

Loup Blanc, your proof is perfect (though you could have said that extending the base field does not change the dimension of $ \left\{C\in K^{n\times n}\mid AC \equal{} CB\right\}$; this is trivial, of course, when viewed from the right perspective). But why do you assume $ A$ and $ B$ to be nilpotent?

Here is my proof:

[b]Rough plan of proof:[/b]
[i]Step 1.[/i] By a dimension argument, we show that for every $ k\in\left\{1,2,...,n\right\}$, the vector space $ \left\{C\in K^{n\times n}\mid AC \equal{} CB\right\}$ contains a nonzero matrix $ U$ such that all columns of $ U$ except for the $ k$-th one are zero. Using this, we prove that the matrix $ B$ is diagonal.
[i]Step 2.[/i] By a symmetry argument, we conclude that $ A$ is diagonal.
[i]Step 3.[/i] By a dimension argument, we show that the vector space $ \left\{C\in K^{n\times n}\mid AC \equal{} CB\right\}$ contains a nonzero matrix $ P$ such that all columns of $ P$ are equal. Using this, we prove that $ B \equal{} \lambda\cdot I_n$ for some $ \lambda\in K$.
[i]Step 4.[/i] By a symmetry argument, we conclude that $ A \equal{} \mu\cdot I_n$ for some $ \mu\in K$.
[i]Step 5.[/i] We show that $ \lambda\equal{}\mu$ and solve the problem.

[b]Detailed proof:[/b]

If $ U$ is a matrix, and $ i$ and $ j$ are two integers, then we denote by $ U_{i,j}$ the entry of the matrix $ U$ in the $ i$-th row and the $ j$-th column.

Define a map $ t: K^{n\times n}\to K^{n\times n}$ by $ t\left(X\right) \equal{} X^T$ for any matrix $ X\in K^{n\times n}$. Then, $ t$ is an isomorphism of $ K$-vector spaces.

[i]Step 1.[/i]

Let $ W \equal{} \left\{C\in K^{n\times n}\mid AC \equal{} CB\right\}$. Obviously, $ W$ is a vector subspace of the $ K$-vector space $ K^{n\times n}$. The problem asks us to prove that if $ \dim W > n\left(n \minus{} 1\right)$, then $ \dim W \equal{} n^2$. So assume that $ \dim W > n\left(n \minus{} 1\right)$.

Let $ k\in\left\{1,2,...,n\right\}$ be arbitrary. Define a vector subspace $ S_k$ of $ K^{n\times n}$ by

$ S_k \equal{} \left\{C\in K^{n\times n}\mid C_{i,j} \equal{} 0\text{ for all }\left(i,j\right)\in\left\{1,2,...,n\right\}^2\text{ with }j\neq k\right\}$
$ \equal{} \left\{C\in K^{n\times n}\mid \text{all columns of the matrix }C\text{ except for the }k\text{ \minus{} th one are zero}\right\}$.

(When I say "all columns of the matrix $ C$ except for the $ k$-th one are zero", I include the case that the $ k$-th column is zero as well.)

Then, $ \dim S_k \equal{} n$. But [url=http://www.mathlinks.ro/viewtopic.php?t=260438]a known formula[/url] yields

$ \dim\left(W \plus{} S_k\right) \equal{} \underbrace{\dim W}_{ > n\left(n \minus{} 1\right)} \plus{} \underbrace{\dim S_k}_{ \equal{} n} \minus{} \dim\left(W\cap S_k\right)$
$ > n\left(n \minus{} 1\right) \plus{} n \minus{} \dim\left(W\cap S_k\right) \equal{} n^2 \minus{} \dim\left(W\cap S_k\right)$,

so that

$ \dim\left(W\cap S_k\right) > n^2 \minus{} \dim\left(W \plus{} S_k\right)\geq n^2 \minus{} n^2$     (since $ W \plus{} S_k\subseteq K^{n\times n}$ yields $ \dim\left(W \plus{} S_k\right)\leq\dim K^{n\times n} \equal{} n^2$)
$ \equal{} 0$.

Thus, there exists a nonzero element $ U\in W\cap S_k$. This element satisfies $ AU \equal{} UB$ (since $ U\in W$), but also $ U_{i,j} \equal{} 0$ for all $ \left(i,j\right)\in\left\{1,2,...,n\right\}^2$ with $ j\neq k$ (since $ U\in S_k$). Since $ U\neq 0$, there exists a pair $ \left(a,b\right)\in\left\{1,2,...,n\right\}^2$ satisfying $ U_{a,b}\neq 0$; this pair must then satisfy $ b \equal{} k$ (since $ b\neq k$ would yield $ U_{a,b} \equal{} 0$, contradicting $ U_{a,b}\neq 0$), so we obtain $ U_{a,k}\neq 0$.

For any $ j\in\left\{1,2,...,n\right\}$ with $ j\neq k$, we now have

$ \left(AU\right)_{a,j} \equal{} \sum_{p \equal{} 1}^nA_{a,p}\underbrace{U_{p,j}}_{ \equal{} 0,\text{ since }j\neq k} \equal{} 0$

and

$ \left(UB\right)_{a,j} \equal{} \sum_{p \equal{} 1}^nU_{a,p}B_{p,j} \equal{} \sum_{p \equal{} k}^kU_{a,p}B_{p,j}$
(here we replaced the $ \sum_{p \equal{} 1}^n$ sign by an $ \sum_{p \equal{} k}^k$ sign, since all addends for $ p\neq k$ are zero, since $ U_{a,p} \equal{} 0$ for all $ p\neq k$)
$ \equal{} U_{a,k}B_{k,j}$.

Thus,

$ 0 \equal{} \left(AU\right)_{a,j} \equal{} \left(UB\right)_{a,j} \equal{} U_{a,k}B_{k,j}$. Since $ U_{a,k}\neq 0$, this becomes $ 0 \equal{} B_{k,j}$.

Thus, for every $ k\in\left\{1,2,...,n\right\}$ and every $ j\in\left\{1,2,...,n\right\}$ with $ j\neq k$, we have $ 0 \equal{} B_{k,j}$. That is, the matrix $ B$ is diagonal.

[i]Step 2.[/i]

In Step 1, we have proven that

[b](1)[/b] If $ A\in K^{n\times n}$ and $ B\in K^{n\times n}$ are two matrices satisfying $ \dim W > n\left(n \minus{} 1\right)$, where $ W \equal{} \left\{C\in K^{n\times n}\mid AC \equal{} CB\right\}$, then $ B$ is diagonal.

Upon renaming $ A$, $ B$, $ C$ and $ W$ as $ X$, $ Y$, $ D$ and $ V$, this becomes:

[b](2)[/b] If $ X\in K^{n\times n}$ and $ Y\in K^{n\times n}$ are two matrices satisfying $ \dim V > n\left(n \minus{} 1\right)$, where $ V \equal{} \left\{D\in K^{n\times n}\mid XD \equal{} DY\right\}$, then $ Y$ is diagonal.

Now, back to our problem. We set $ X \equal{} B^T$ and $ Y \equal{} A^T$, and let $ V \equal{} \left\{D\in K^{n\times n}\mid XD \equal{} DY\right\}$. Then,

$ V \equal{} \left\{D\in K^{n\times n}\mid XD \equal{} DY\right\} \equal{} \left\{D\in K^{n\times n}\mid B^TD \equal{} DA^T\right\}$
$ \equal{} \left\{D\in K^{n\times n}\mid \left(D^TB\right)^T \equal{} \left(AD^T\right)^T\right\}$     (since $ B^TD \equal{} \left(D^TB\right)^T$ and $ DA^T \equal{} \left(AD^T\right)^T$)
$ \equal{} \left\{D\in K^{n\times n}\mid D^TB \equal{} AD^T\right\} \equal{} \left\{D\in K^{n\times n}\mid AD^T \equal{} D^TB\right\}$
$ \equal{} \left\{D\in K^{n\times n}\mid At\left(D\right) \equal{} t\left(D\right)B\right\}$
$ \equal{} t^{ \minus{} 1}\left(\left\{C\in K^{n\times n}\mid AC \equal{} CB\right\}\right) \equal{} t^{ \minus{} 1}\left(W\right)$,

so that

$ \dim V \equal{} \dim\left(t^{ \minus{} 1}\left(W\right)\right) \equal{} \dim W$    (since $ t$ is an isomorphism of $ K$-vector spaces)
$ > n\left(n \minus{} 1\right)$.

Hence, by [b](2)[/b], we conclude that $ Y$ is diagonal. Since $ Y \equal{} A^T$, this means that $ A^T$ is diagonal, so that $ A$ is diagonal.

As a result, we now know that both matrices $ A$ and $ B$ are diagonal.

[i]Step 3.[/i]

Now, define a vector subspace $ T$ of $ K^{n\times n}$ by

$ T \equal{} \left\{C\in K^{n\times n}\mid C_{i,j} \equal{} C_{i,1}\text{ for all }\left(i,j\right)\in\left\{1,2,...,n\right\}^2\right\}$
$ \equal{} \left\{C\in K^{n\times n}\mid \text{every column of the matrix }C\text{ is equal to the first one}\right\}$
$ \equal{} \left\{C\in K^{n\times n}\mid \text{all columns of the matrix }C\text{ are equal}\right\}$.

Then, $ \dim T \equal{} n$. But [url=http://www.mathlinks.ro/viewtopic.php?t=260438]a known formula[/url] yields

$ \dim\left(W \plus{} T\right) \equal{} \underbrace{\dim W}_{ > n\left(n \minus{} 1\right)} \plus{} \underbrace{\dim T}_{ \equal{} n} \minus{} \dim\left(W\cap T\right)$
$ > n\left(n \minus{} 1\right) \plus{} n \minus{} \dim\left(W\cap T\right) \equal{} n^2 \minus{} \dim\left(W\cap T\right)$,

so that

$ \dim\left(W\cap T\right) > n^2 \minus{} \dim\left(W \plus{} T\right)\geq n^2 \minus{} n^2$     (since $ W \plus{} T\subseteq K^{n\times n}$ yields $ \dim\left(W \plus{} T\right)\leq\dim K^{n\times n} \equal{} n^2$)
$ \equal{} 0$.

Thus, there exists a nonzero element $ P\in W\cap T$. This element satisfies $ AP \equal{} PB$ (since $ P\in W$), but also $ P_{i,j} \equal{} P_{i,1}$ for all $ \left(i,j\right)\in\left\{1,2,...,n\right\}^2$ (since $ P\in T$). Since $ P\neq 0$, there exists a pair $ \left(a,b\right)\in\left\{1,2,...,n\right\}^2$ satisfying $ P_{a,b}\neq 0$; thus, $ P_{a,1}\neq 0$ (since $ P_{a,b} \equal{} P_{a,1}$).

For any $ j\in\left\{1,2,...,n\right\}$, we now have

$ \left(AP\right)_{a,j} \equal{} \sum_{p \equal{} 1}^nA_{a,p}P_{p,j} \equal{} \sum_{p \equal{} a}^aA_{a,p}P_{p,j}$
(here we replaced the $ \sum_{p \equal{} 1}^n$ sign by an $ \sum_{p \equal{} a}^a$ sign, since all addends for $ p\neq a$ are zero, since $ A_{a,p} \equal{} 0$ for all $ p\neq a$, since the matrix $ A$ is diagonal)
$ \equal{} A_{a,a}P_{a,j} \equal{} A_{a,a}P_{a,1}$

$ \left(PB\right)_{a,j} \equal{} \sum_{p \equal{} 1}^nP_{a,p}B_{p,j} \equal{} \sum_{p \equal{} j}^jP_{a,p}B_{p,j}$
(here we replaced the $ \sum_{p \equal{} 1}^n$ sign by an $ \sum_{p \equal{} j}^j$ sign, since all addends for $ p\neq j$ are zero, since $ B_{p,j} \equal{} 0$ for all $ p\neq j$, since the matrix $ B$ is diagonal)
$ \equal{} P_{a,j}B_{j,j} \equal{} P_{a,1}B_{j,j} \equal{} B_{j,j}P_{a,1}$.

Thus,

$ A_{a,a}P_{a,1} \equal{} \left(AP\right)_{a,j} \equal{} \left(PB\right)_{a,j} \equal{} B_{j,j}P_{a,1}$,

so that $ A_{a,a} \equal{} B_{j,j}$ (since $ P_{a,1}\neq 0$).

Thus, for every $ j\in\left\{1,2,...,n\right\}$, we have $ A_{a,a} \equal{} B_{j,j}$. Hence,

$ B \equal{} \mathrm{diag}\left(B_{1,1},B_{2,2},...,B_{n,n}\right)$ (since $ B$ is a diagonal matrix)
$ \equal{} \mathrm{diag}\left(A_{a,a},A_{a,a},...,A_{a,a}\right) \equal{} A_{a,a}\cdot I_n$.

Denote $ \lambda \equal{} A_{a,a}$; then, this becomes $ B \equal{} \lambda\cdot I_n$.

[i]Step 4.[/i]

In Step 3, we have proven that

[b](3)[/b] If $ A\in K^{n\times n}$ and $ B\in K^{n\times n}$ are two matrices satisfying $ \dim W > n\left(n \minus{} 1\right)$, where $ W \equal{} \left\{C\in K^{n\times n}\mid AC \equal{} CB\right\}$, then there exists some $ \lambda\in K$ such that $ B \equal{} \lambda\cdot I_n$.

Upon renaming $ A$, $ B$, $ C$, $ W$ and $ \lambda$ as $ X$, $ Y$, $ D$, $ V$ and $ \mu$, this becomes:

[b](4)[/b] If $ X\in K^{n\times n}$ and $ Y\in K^{n\times n}$ are two matrices satisfying $ \dim V > n\left(n \minus{} 1\right)$, where $ V \equal{} \left\{D\in K^{n\times n}\mid XD \equal{} DY\right\}$, then there exists some $ \mu\in K$ such that $ Y \equal{} \mu\cdot I_n$.

Now, back to our problem. We set $ X \equal{} B^T$ and $ Y \equal{} A^T$, and let $ V \equal{} \left\{D\in K^{n\times n}\mid XD \equal{} DY\right\}$. Then, we already have proven that $ \dim V > n\left(n \minus{} 1\right)$.

Hence, by [b](4)[/b], we conclude that there exists some $ \mu\in K$ such that $ Y \equal{} \mu\cdot I_n$. Thus, $ A \equal{} \left(A^T\right)^T \equal{} Y^T \equal{} \left(\mu\cdot I_n\right)^T \equal{} \mu\cdot I_n$.

[i]Step 5.[/i]

So we know that $ A \equal{} \mu\cdot I_n$ and $ B \equal{} \lambda\cdot I_n$. Thus,

[b](5)[/b] $ \dim W \equal{} \dim\left\{C\in K^{n\times n}\mid AC \equal{} CB\right\}$
$ \equal{} \dim\left\{C\in K^{n\times n}\mid \mu\cdot I_n\cdot C \equal{} C\cdot\lambda\cdot I_n\right\}$
$ \equal{} \dim\left\{C\in K^{n\times n}\mid \mu C \equal{} \lambda C\right\} \equal{} \dim\left\{C\in K^{n\times n}\mid\left(\mu \minus{} \lambda\right)C \equal{} 0\right\}$.

Now, $ \lambda \equal{} \mu$ (since if we had $ \lambda\neq\mu$, then [b](5)[/b] would become

$ \dim W \equal{} \dim\left\{C\in K^{n\times n}\mid\left(\mu \minus{} \lambda\right)C \equal{} 0\right\} \equal{} \dim\left\{C\in K^{n\times n}\mid C \equal{} 0\right\}$      (since $ \lambda\neq\mu$ yields $ \mu \minus{} \lambda\neq 0$, so that $ \mu \minus{} \lambda$ is invertible)
$ \equal{} \dim 0 \equal{} 0$,

contradicting $ \dim W > n\left(n \minus{} 1\right)$). Thus, [b](5)[/b] becomes

$ \dim W \equal{} \dim\left\{C\in K^{n\times n}\mid\left(\mu \minus{} \lambda\right)C \equal{} 0\right\} \equal{} \dim\left\{C\in K^{n\times n}\mid\left(\mu \minus{} \mu\right)C \equal{} 0\right\}$
$ \equal{} \dim\left\{C\in K^{n\times n}\mid 0 \equal{} 0\right\} \equal{} \dim K^{n\times n} \equal{} n^2$,

qed.

Sorry for the use of copypaste in the proof, but that meant less chances to make mistakes and thus less proofreading for me...

  darij

"Darij wrote:
Loup Blanc, your proof is perfect. But why do you assume  and  to be nilpotent?"

I proved only that it is sufficient to show the result in the case: $ A,B$ are nilpotent matrices. But it remains to do that !

Now I go to read your proof; I think that it is a long way.

A short proof applying some of the ideas introduced earlier in the posts:

Consider the linear homomorphism of $ K^{n\times n}$ defined by $ \psi: C\mapsto AC-CB$. By assumption we have $ \dim [Im(\psi)]<n$. Introduce the "column" subspaces $ V_k=\{U\in K^{n\times n}\,|\,U_{ij}\not= 0\Longrightarrow j=k\}$ for $ k=1,\ldots,n$ and note that $ V_k\simeq K^n$.

Therefore, for each $ k$ there exists $ C\not=0\in V_k: AC-CB=0$. This yields for all $ i,j=1,\ldots,n$ and $ j\not=k$ the identity: $ 0=C_{ik}B_{kj}$. Since $ C\not=0$, we get $ B_{kj}=0$ for all $ j\not=k$. Stepping through all the different $ k$'s, we conclude that $ B$ is a diagonal matrix. Similarly, applying the "row" subspaces $ W_k=\{U\in K^{n\times n}\,|\,U_{ij}\not= 0\Longrightarrow i=k\}$ for $ k=1,\ldots,n$, we conclude $ A$ is of diagonal form, too.

(Alternatively, perform matrix transposition of the original problem to conclude that $ A$ is of diagonal form, too.).

We conclude, that $ Ker(\psi )=\{C\in K^{n\times n}\,|\,\forall i,j=1,\ldots,n: (A_{ii}-B_{jj})C_{ij}=0\}$. By assumption, we know that the set $ \{(i,j)\in\{1,\ldots,n\}^2\,|\,A_{ii}=B_{jj}\}$ contains more than $ n(n-1)$ elements. Hence, there is some $ i'$ (respectively some $ j'$) with $ \forall j: A_{i'i'}=B_{jj}$ (respectively with $ \forall i: A_{ii}=B_{j'j'}$), i.e. putting all together $ A=B=\lambda I_n$ and $ Ker(\psi)=K^{n\times n}$.

[quote="loup blanc"]"Darij wrote:
Loup Blanc, your proof is perfect. But why do you assume  and  to be nilpotent?"

I proved only that it is sufficient to show the result in the case: $ A,B$ are nilpotent matrices. But it remains to do that ![/quote]

Ah! I was actually idiot enough to forget that equal eigenvalues don't imply the matrix to be diagonal...

Anyway, your argument can be used to replace Steps 3-5 in my proof.
I think you will be able to understand my proof just by reading the rough plan (if it is correct :D ).

Hjbrasch: yeah, this works; you used steps 1-2 from my proof, but the rest of your proof is simpler.

  darij

[quote]
I tried to understand tmrfea's proof, but somehow I kept petering out on step 1). tmrfea, can you please write it up less "dynamically" ("we can perform" etc.) and more formally? (It does look somewhat similar to mine proof, I just don't understand it...)
[/quote]

Ok. I will try again.

In step 1, I first make an isomorphism:

$ A: K^{n\times n}\rightarrow K^{n^{2}},$ defined by

$ A: (ij)\mathrm { - th\; entry \;of \;an \;element \;in \;} K^{n\times n} \mapsto \\
((i - 1)n + j)\mathrm{ - th\; coordinate\; of\; an\; element \;in\; }K^{n^{2}}$.

We denote by $ E_{ij}$ the matrix, which has $ ij$-th entry equal to $ 1$ and all the other entries equal to $ 0$. So:

$ A\left(E_{11}\right) = (1,0,\ldots,0)$
$ A\left(E_{12}\right) = (0,1,0,\ldots,0)$
$ \vdots$
$ A\left(E_{ij}\right) = (\underbrace{0,\ldots,0}_{n(i - 1) + j-1 \; \mathrm{of \; them}},1,0,\ldots,0)$
$ \vdots$
$ A\left(E_{nn}\right) = (0,\ldots,0,1)$

Since the matrices $ E_{11}, E_{12}, \ldots, E_{nn}$ form the basis for $ K^{n\times n}$ and $ A$ is an isomorphism, $ A\left(E_{11}\right), A\left(E_{12}\right), \ldots, A\left(E_{nn}\right)$ form the basis for $ K^{n^2}$.

Now in our problem we have the subspace $ W$ in $ K^{n\times n}$ with dimension $ n^{2} - n + s,$ where $ s > 0$. Since $ W$ is finite dimensional, we can choose its basis, say $ M_1, M_2,\ldots, M_{n^{2} - n + s}$.

Now we map the chosen basis with $ A$ to $ K^{n^{2}}$.

Again since $ A$ is an isomorphism and $ M_1, M_2,\ldots, M_{n^{2} - n + s}$ are lineary independent, also $ A\left(M_1\right), A\left(M_2\right),\ldots, A\left(M_{n^{2} - n + s}\right)$ are lineary independent. Therefore, they are the basis of the subspace $ W^{\prime}$ in $ K^{n^{2}}$, which is in fact $ A(W)$. However,

$ A\left(M_1\right) = (m^{1}_{11},m^{1}_{12},\ldots,m^{1}_{nn})$
$ A\left(M_2\right) = (m^{2}_{11},m^{2}_{12},\ldots,m^{2}_{nn})$
$ \vdots$
$ A\left(M_{n^{2} - n + s}\right) = (m^{n^{2} - n + s}_{11},m^{n^{2} - n + s}_{12},\ldots,m^{n^{2} - n + s}_{nn})$

Now we put the coefficients $ m^{1}_{11}, \ldots,m^{1}_{nn},\ldots, m^{n^{2} - n + s}_{nn}$ into $ (n^{2} - n + s)\times n^{2}$ matrix $ S$, where $ i\mathrm m{ - th\; row}$ represents coeficients of $ A\left(M_i\right)$ and $ j\mathrm m{ - th\; column}$ represents $ j\mathrm{ - th}$ basis vector of our basis in $ K^{n^{2}}$. ($ j\mathrm{ - th}$ basis vector is $ A\left(E_{\left\lfloor \frac {j}{n} \right\rfloor + 1; j - n\left\lfloor \frac {j}{n} \right\rfloor}\right)),$ where $ \left\lfloor \frac {j}{n} \right\rfloor$ is a whole part of $ \frac {j}{n}$.

Now we reduce $ S$ into its reduced row echelon form (say $ S^{\circ}$) via just permuting rows and adding some multiple of some row to another. Since with the mentioned transformations we do not do anything else, than just move the vectors from $ W^{\prime}$ or add some multiple of one vector of $ W^{\prime}$ to another,  the new rows represent some new basis of $ W^{\prime}$.

Since my step one does not do anything else then just claim, that:

[quote]
1. There exists a row ($ i$) and a column ($ j$) for which there exists an element $ C$ in $ W$ , which has $ ik$-th entry equal to $ 1$ (where $ k$ is an arbitary column), all the other entries in $ i$-th row and $ j$-th column equal to $ 0$  and at most  ($ n - 1$) other non-zero entries. Similarly there exists an element $ C$  in $ W$, which has $ kj$-th entry equal to $ 1$  (where $ k$ is an arbitary row), all the other entries in $ i$-th row and $ j$-th column equal to $ 0$ and at most ($ n - 1$) other non-zero entries.
[/quote]

I can also permute columns of $ S^{\circ}$, since it is not important for me, for which row $ i$ or column $ j$ it goes (hence for which $ E_{ik}$-s and which $ E_{kj}$-s). I also do not destroy vectors in $ W^{\prime}$, since I just permute its coordinates (and the basis of $ K^{n^{2}}$). So I get $ S^{\ast}$.

However, I do not even need to permute columns, just that if I do so, it is more straightforward to see, that there are at most $ n - s$ other non-zero coordinates of $ A(M^{\circ}_{i})$ except one entry, which is $ 1$ and that those uknown $ n - s$ other non-zero coordinates are the sam for all new base vectors of $ W^{\prime}$ ($ A(M^{\circ}_{i})$ is the $ i\mathrm{ - th}$ row in $ S^{\circ}$). So putting the matrix in the reduced row echelon form and permuting columns, gives us pivots in the first $ n^{2} - n + s$ columns. Hence there remain at most $ n - s$ columns, which are not necessarilly $ 0$.

Now we can return to $ S^{\circ}$. So we can conclude, that each row has one coordinate equal to $ 1$ and at most $ n - s$ other non-zero coordinates, but they are the same for all rows.

So since we know, that all row vectors of $ S^{\circ}$ are in $ W^{\prime} = A(W)$, we can get $ M^{\circ}_{i}\in W$ from $ A(M^{\circ}_{i})$ with $ A^{ - 1}$. Therefore $ M^{\circ}$ matrices will have one entry equal to $ 1$ and at most $ n - s$ other non-zero entries (but same for all new base matrices). We denote them by $ t_1, t_2, \ldots, t_{n - s}$. Since there are $ n^{2} - n + s$ matrices in new basis of $ W$ and each has one known  entry ($ 1$) but pairwise on the different positions (but not on $ t_1,\ldots, t_{n - s}$), we can find a matrix with $ ij$-th position equal to $ 1$ and all the others except $ t_1,\ldots, t_{n - s}$ equal to $ 0$.

Finally, since there are just ($ n - s\leq n - 1$) potentially nonzero unknown entries $ t_1, t_2, \ldots, t_{n - s}$, there are at most $ n - 1$ unknown rows and $ n - 1$ unknown columns of the new matrices. Since they are the same for all matrices, there exists a row ($ i$) and a column ($ j$) which is completely known for all matrices (there is exactly one $ 1$ entry and all the remaining are $ 0$ or there are just $ 0$ entries). But since we know from above, that there exists a matrix, which has $ kl$-th entry equal to $ 1$ if $ kl$-th entry is not one of $ t_1,\ldots, t_{n - s}$, we can chose $ 2n - 1$ matrices from $ M^{\circ} = \left\{M^{\circ}_{1},\ldots,M^{\circ}_{n^{2} - n + s}\right\}$, which satisfy

[quote]
1. There exists a row ($ i$) and a column ($ j$) for which there exists an element $ C$ in $ W$ , which has $ ik$-th entry equal to $ 1$ (where $ k$ is an arbitary column), all the other entries in $ i$-th row and $ j$-th column equal to $ 0$  and at most  ($ n - 1$) other non-zero entries. Similarly there exists an element $ C$  in $ W$, which has $ kj$-th entry equal to $ 1$  (where $ k$ is an arbitary row), all the other entries in $ i$-th row and $ j$-th column equal to $ 0$ and at most ($ n - 1$) other non-zero entries.
[/quote].


Suppose $ 2a\minus{}3b \equal{} \minus{}23$. Given that $ a$ and $ b$ are consecutive integers, and $ a<b$, what is the value of $ a$?

b=a+1, so this means that 2a-3a-3=-23, or -a=-20, so a is 20.


Solve in $ \mathbb{R}$ the equation : $ \log_2(\sin x)\plus{}\log_3(\tan x)\equal{}\log_4(\cos^2 x)\plus{}\log_5(\cot x)$ .

Aceasta problema este inclusa si in subiectul de concurs online al site-ului matefbc.As ruga sa nu se posteze o rezolvare pana la ora 22:00 a acestei zile. Multumesc mult!

Please don't post a solution until 10 a.m.This problem is proposed in an online competition.

$ \frac{{\log \sin x}}
{{\log 2}} \plus{} \frac{{\log \tan x}}
{{\log 3}} \minus{} \frac{{\log \cos x}}
{{\log 2}} \plus{} \frac{{\log \tan x}}
{{\log 5}} \equal{} 0$

$ \frac{{\log \tan x}}
{{\log 2}} \plus{} \frac{{\log \tan x}}
{{\log 3}} \plus{} \frac{{\log \tan x}}
{{\log 5}} \equal{} \log \tan x\left( {\frac{1}
{{\log 2}} \plus{} \frac{1}
{{\log 3}} \plus{} \frac{1}
{{\log 5}}} \right) \equal{} 0$

$ \tan x \equal{} 1 \Rightarrow x \equal{} \frac{\pi }
{4} \plus{} k\pi$