Wikipedia:Reference desk/Archives/Mathematics/2016 July 10

Mathematics desk
< July 9 << Jun | July | Aug >> July 11 >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


July 10

edit

Cubic of  

edit
 
 
 

After a long travel, I got here

 
 

Now what? יהודה שמחה ולדמן (talk) 09:23, 10 July 2016 (UTC)[reply]

There's nothing more that you can do with it. Sin(1°) cannot be written algebraically without using complex numbers, because your first equation is an example of casus irreducibilis. Loraof (talk) 14:44, 10 July 2016 (UTC). (Technically casus irreducibilis refers to cases in which the constant term in the cubic equation is rational, but the same basic idea applies here too.) Loraof (talk) 14:52, 10 July 2016 (UTC)[reply]
See also Angle trisection#Angles which can be trisected. Loraof (talk) 14:57, 10 July 2016 (UTC)[reply]
OK. Is there a math Generalization for the Angle bisector theorem, lets say an Angle trisector theorem and so on? יהודה שמחה ולדמן (talk) 19:05, 10 July 2016 (UTC)[reply]
Not that I know of, but you might be interested in Morley's trisector theorem. Loraof (talk) 20:00, 10 July 2016 (UTC)[reply]

Let me solve it for you. 0.141120008 for all practical purposes in building tree houses for kids on earth. 175.45.116.61 (talk) 23:39, 10 July 2016 (UTC)[reply]

Tell me when to laugh, genius (sarcasm). יהודה שמחה ולדמן (talk) 09:22, 11 July 2016 (UTC)[reply]
I looked at this page here and after calculating I got to   .
But it seems that   if we take the real cube root of 1. The imaginary roots give us  . why? יהודה שמחה ולדמן (talk) 13:26, 12 July 2016 (UTC)[reply]
Every angle 3theta has not one but three angles theta. In the case of 3theta = 90°, these solutions for theta are 30°, 30°+120°=150°, and 30°–120°=–90°. The sines of these angles are 1/2, 1/2, and –1 respectively. Loraof (talk) 14:48, 12 July 2016 (UTC)[reply]
You mean   . But how would these 3 values give different results for   ? יהודה שמחה ולדמן (talk) 15:19, 12 July 2016 (UTC)[reply]
90°+360°k is the same thing as 90°, and is normally written as simply 90°. These three values of theta have three individual values of their sines: 1/2, 1/2, and –1. No matter which of these you substitute into the cubic equation, you get sin 90°=1. That shows that each of them is a solution of the equation in which the value of sin(3theta) is specified as 1. Loraof (talk) 20:35, 12 July 2016 (UTC)[reply]
So your'e telling me that for sin(30°) we must choose one out of 3 roots of   over the complex?
We don't get it right away inside the formula? Show me what would you do. יהודה שמחה ולדמן (talk) 17:48, 14 July 2016 (UTC)[reply]
Read Cubic function#Cardano's method, especially the offset equation after equation (5), to see how to use the complex cube roots of 1. There   is one of the complex cube roots of 1, as defined earlier in that section. So yes, complex numbers are inevitably involved in algebraically writing the solutions of your original cubic equation. You cannot avoid them without using trigonometry in the way discussed in the section Cubic function#Trigonometric and hyperbolic solutions. If you want to compute a numerical value for the sine of 30°, you can use the rational root test—if it shows (as it will in this case) that there is a rational root of the cubic   you can factor out a rational root using polynomial long division and then use the quadratic formula to solve for the other two roots; then one of these three roots is your desired answer for the sine of the 1/3 angle. To decide which one, check what quadrant of the complex plane you expect the 1/3 angle to be in and pick the answer that fits.
But for most angles other than 90°, the rational root test will show that there are no rational solutions for the cubic equation. Then, as I said earlier you would have casus irreducibilis and cannot algebraically avoid the appearance of complex numbers; so to find the sine of the 1/3 angle numerically you would have to use numerical analysis—probably some method like Newton's method.
This thread is about to be archived in a little over an hour, so if you need to continue this conversation you can do so on my talk page. Loraof (talk) 22:47, 14 July 2016 (UTC)[reply]

Fast Boolean Matrix Multiplication

edit

Hi, what is the the minimal k for which there exists an algorithm that solves matrix multiplication for boolean matrices in time  ? I know that the answer for real-valued matrices is   (where  ), but I don't know what's the best algorithm for boolean matrices. 31.154.81.27 (talk) 10:36, 10 July 2016 (UTC)[reply]

Edit: I also assume the matrices to be upper triangular.31.154.81.27 (talk) 10:50, 10 July 2016 (UTC)[reply]

According to our article it can be done in O(n2) expected time. --RDBury (talk) 11:24, 10 July 2016 (UTC)[reply]
Thank you! But the algorithm citated in that article has matrices for which it runs in cubic time (it has quadratic time for random pair of matrices). Do you know some algorithm that runs in expected/ deterministic quadratic time for every pair of boolean matrices? 31.154.81.27 (talk) 11:49, 10 July 2016 (UTC)[reply]
I notice that the article mentions two distinct types of Boolean matrix: built on the operations AND/OR and AND/XOR respectively, and this might confuse things a bit. I assume that the former is the subject of this question, and the primary topic of the article.
The reference does make the following statement:
At present there is only one algorithm known to multiply Boolean matrices in O(nβ) operations, β < 3. It has been observed [see Fisher and Meyer (1971), Furman (1970), Munro (1971)] that two Boolean matrices may be multiplied in O(n 1og27) operations. One uses the method of Strassen (1969) to obtain the real integer product of A and B and normalizes the result by replacing all nonzero entries with 1.
The description appears to suggest that this is a deterministic time. As to an algorithm that would run in exactly (or even arbitrarily close to) quadratic time for arbitrary matrices, such seems unlikely to exist, and even less likely to be known. I guess that the algorithm giving close to O(n2) relies on the sum-of-products being known as soon as one nonzero term is found, thus not having to evaluate the remainder of the sum. —Quondum 15:30, 10 July 2016 (UTC)[reply]
Thank you for the citation. I hadn't noticed it when reading this article. It's helpful for me! 31.154.81.65 (talk) 05:51, 12 July 2016 (UTC)[reply]