Over a million developers have joined DZone.

Smith's Determinant

· Big Data Zone

Learn how you can maximize big data in the cloud with Apache Hadoop. Download this eBook now. Brought to you in partnership with Hortonworks.

Here’s a curious identity I ran across while browsing Knuth’s magnum opus.

\[\left|    \begin{array}{llll}       \gcd(1,1) & \gcd(1,2) & \ldots & \gcd(1, n) \\       \gcd(2,1) & \gcd(2,2) & \ldots & \gcd(2, n) \\       \vdots & \vdots & & \vdots \\       \gcd(n,1) & \gcd(n,2) & \ldots & \gcd(n, n)     \end{array}\right| = \varphi(1) \varphi(2) \cdots \varphi(n) \>

Here gcd(ij) is the greatest common divisor of i and j, and φ(n) is Euler’s phi function, the number of positive integers less than or equal to n and relatively prime to n.

The more general version of Smith’s determinant replaces gcd(ij) above with f( gcd(ij) ) for an arbitrary function f.

As a hint at a proof, you can do column operations on the matrix to obtain a triangular matrix with φ(i) in the ith spot along the diagonal.

Source: TAOCP vol 2, section 4.5.2, problem 42.

Hortonworks DataFlow is an integrated platform that makes data ingestion fast, easy, and secure. Download the white paper now.  Brought to you in partnership with Hortonworks

Topics:

Published at DZone with permission of John Cook, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}