Finding Linearly Dependent Rows in a Large Matrix

[Big Data Alan]

I have a large real symmetric square matrix (with millions of rows/columns). How can I identify the sets of rows that are linearly dependent?

More generally, can I determine linear independence of rows with a continuous function where, say, the function is 1.0 for a row that is linearly independent and 0.0 when it is linearly dependent. I am interested in identifying rows that are almost linearly dependent. For example, say that due to round-off error rows A and B are identical in all columns except that they differ by 1 part per million in one column's entries.

 

[AlephZero]

If your matrix with 1,000,000 rows is full, the answer is "with great difficulty", unless you have access to a world-class supercomputing facility.

If the matrix is sparse, a good way would be to find the smallest eigenvalues or singular values. The corresponding vectors give you linear combinations that are "almost" linearly dependent.

 

[Big Data Alan]

Thanks. I should have mentioned that it is a very sparse matrix. Most rows have just a handful of non-zero entries although a few rows are exceptionally dense. I have been using the Mahout's Singular Value Decomposition program http://mahout.apache.org to find the eigenvectors. This program rejects the near-zero eigenvalue (in its "cleaning" stage) but I will check it out to see what it can tell me about the linearly dependent rows.

 

[Big Data Alan]

In response to the questions posted by Windowmaker - which I received notice of but cannot find within this thread: What are you doing with a matrix that big? Is it the first LA course?

I am afraid that I have strayed far from my physics education. I have a collection of nearly 2 billion packets that transited the gateways connecting our corporate network to the Internet over a few days. These involve 2.4 million unique IP addresses. So I created a 2.4M by 2.4M matrix where the indices map to the IP addresses and the elements are the number of packets exchanged between them. Perhaps surprisingly you can find individual eigenvectors fairly quickly but finding all of them is not practical. The first few eigenvectors primarily involve sums and differences of the key nodes (in terms of numbers of IPs they are in contact with and the numbers of packets exchanged).

The sorts of questions I hope the eigenvectors will answer are:
1) Which are the principal nodes in the network?
2) Given a node, which nodes are sending similar numbers of packets to the same other nodes? (For example, I have noticed similar network attacks emanating from multiple IPs and would like an algorithmic approach to identifying the clones/copy-cats.)
3) Which nodes share a structural similarity? (For example, given the IP address of the DNS server can I figure out which one is the backup DNS server?)

Note that the matrix elements are all integers; my comment about round-off error was really about minor differences in packets counts due to a) time-limited data sample, b) lost packets being resent, ...

 

[blue_raver22]

I understand the importance of identifying linearly dependent rows in a large matrix. This information can provide valuable insights into the relationships between the rows and can help improve the accuracy and efficiency of various analyses and computations.

To identify linearly dependent rows in a large matrix, there are a few approaches that you can consider. One method is to use Gaussian elimination, which involves transforming the matrix into row-echelon form and then checking for any rows with all zero entries. These rows would be considered linearly dependent. This method can be computationally intensive, especially for large matrices, but it can provide an exact solution.

Another approach is to use a linear algebra library or software tool that has built-in functions for identifying linearly dependent rows. These tools often have efficient algorithms for handling large matrices and can provide a quicker solution compared to manual methods.

To address your question about determining linear independence with a continuous function, there are a few things to consider. First, it is important to define what is meant by "almost" linearly dependent. This can vary depending on the specific application and the level of precision required. One approach could be to define a threshold for the difference between rows, such as 1 part per million as mentioned in your example. Then, you could use a function that calculates the difference between rows and outputs a value between 0 and 1, with 0 indicating complete linear dependence and 1 indicating complete linear independence.

However, it is worth noting that this approach may not be as accurate as using a method that directly identifies linearly dependent rows. This is because the function may not capture all possible cases of linear dependence, such as when a row is a linear combination of multiple other rows.

In conclusion, identifying linearly dependent rows in a large matrix is an important task that can be approached using various methods and tools. It is important to carefully consider the level of precision required and the limitations of different approaches in order to obtain accurate results.