Let E be the Hilbert space of real symmetric matrices with block diagonal form diag(A, M), where A is n ร n, and M is an l ร l diagonal matrix, with the inner product x, y โก Trace(xy). We assume n + l 1, i.e. allow n = 0 or l = 0. Given x โ E, we write x 0 (x 0) if it is positive semidefinite (positive definite). Let Q : E โ E be a symmetric positive semidefinite linear operator, and ยต = min{ฯ(x) = 0.5 Trace(xQx) : x = 1, x 0}. The problem of testing if ยต = 0 is a significant problem called Homogeneous Programming. On the one hand the feasibility problem in semidefinite programming (SDP) can be formulated as a Homogeneous Programming problem. On the other hand it is related to the generalization of the classic problem of Matrix Scaling. Let โ (0, 1) be a given accuracy, u = Qee, e the identity matrix in E, and N = n + l. We describe a path-following algorithm that in case ยต = 0, in O(
, where D is the operator that maps w โ E to d 1/2 wd 1/2 . Moreover, we use the algorithm to prove: ยต > 0, if and only if there exists d 0 such that DQDe = e, if and only if there exists d 0 such that Qd 0. Thus via this duality the Matrix Scaling problem is a natural dual to the feasibility problem in SDP. This duality also implies that in Blum et al. [Bull. AMS 21 (1989) 1] real number model of computation the decision problem of testing the solvability of Matrix Scaling is both in NP and Co-NP. Although the above complexities can be deduced from our path-following algorithm for general self-concordant Homogeneous Programming and for Matrix Scaling obtained in [Scaling dualities and self-concordant homogeneous programming in finite dimensional spaces,